- 문제
- 제출
각 자리에 0부터 9까지의 자연수가 올 수 있으므로, 한 row에 10개의 space가 있는 matrix를 정의한다.
우선, 첫 번째 자리에는 0을 제외한 모든 수가 올 수 있으므로 matrix의 첫 번째 row에는 첫 번째 자리를 제외한 모든 자리에 1을 넣는다.
그다음은 3가지 경우로 나누어 생각해야 한다.
1. 0이 오는 경우
이 경우에는 이전 숫자가 1이었다가 down 하는 경우만 존재한다. 즉, 이전 숫자가 1이 되는 경우의 수와 같다는 의미이다.
=> cache[i][0] = cache[i-1][1]
2. 9가 오는 경우
이 경우에는 이전 숫자가 8이었다가 up 하는 경우만 존재한다. 즉, 이전 숫자가 8이 되는 경우의 수와 같다는 의미이다.
=> cache[i][9] = cache[i-1][8]
3. 그 외의 모든 경우 (1~8)
N의 경우, 이전 숫자가 N-1이었다가 up 하는 경우와 이전 숫자가 N+1이었다가 down 하는 경우로 나뉜다. 따라서, 이 두 경우의 수를 합한 수가 해당 숫자가 N일 때의 경우의 수라고 할 수 있다.
=> cache[i][j] = cache[i-1][j-1] + cache[i-1][j+1]
N = int(input())
mod = 1000000000
def stairNum(N):
cache = [[0]*10 for _ in range(101)]
for i in range(1,10):
cache[1][i] = 1
for i in range(2,N+1):
for j in range(10):
if j==0:
cache[i][j] = cache[i-1][1]
elif j==9:
cache[i][j] = cache[i-1][8]
else:
cache[i][j] = cache[i-1][j-1] + cache[i-1][j+1]
return sum(cache[N])
print(stairNum(N)%mod)
'Study > [파이썬] 백준온라인' 카테고리의 다른 글
[ 백준/python ] 5585 : 거스름돈 (0) | 2021.07.30 |
---|---|
[백준/python] 9251 : LCS (0) | 2021.07.15 |
[백준/python] 2225: 합분해 (0) | 2021.07.14 |
[백준/python] 11399 : ATM (0) | 2021.07.05 |
[백준/python] 1929 : 소수 구하기 (0) | 2021.01.13 |