[BOJ]10844_쉬운계단
풀이
0을 제외한 모든 숫자는 앞에 올 수 있다.
이때 1~8은 뒤에 올 수 있는 숫자가 총 2종류이다(숫자±1).
하지만 9 뒤엔 오직 숫자 8만이 올 수 있다.
자리수가 2일때를 보자.
맨 뒤에 0이 올 수 있는 경우의 수 - 10이 있다.(1개)
맨 뒤에 1이 올 수 있는 경우의 수 - 21이 있다.(1개)
맨 뒤에 2이 올 수 있는 경우의 수 - 12, 32이 있다.(2개)
이렇게 3자리수까지 구해보면 위와같은 표가 나올 수 있는데 규칙을 찾아보면,
해당 위치의 대각선 위 위치의 숫자들의 합인걸 알 수 있다.
코드
N = int(input())
dp = [[0]*10 for _ in range(N+1)]
for i in range(1, 10):
dp[1][i] = 1
MOD = 1000000000
for i in range(2, N+1):
for j in range(10):
if j == 0:
dp[i][j] = dp[i-1][1]
elif j == 9:
dp[i][j] = dp[i-1][8]
else:
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
print(sum(dp[N]) % MOD)
Author And Source
이 문제에 관하여([BOJ]10844_쉬운계단), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@zioo/BOJ10844쉬운계단저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)