11057번 Python

점화식은 스스로 찾아낼 수는 있었는데 코드로써 식을 대입하지는 못했던 것 같다.

 

0 1 2 3 4 5 6 7 8 9

1자리의 오르막수는 위와 같이 10개이다.

 

# 0이 마지막인 오르막 수
00

# 1이 마지막인 오르막 수
01 11

# 2가 마지막인 오르막 수
02 12 22

2자리의 오르막수는 다음과 같다. 이렇게 해서 2자리는 55개라고 문제에서 나와있는데 사실 55라는 숫자만 봐도 대충 감이 올 사람을 왔을 수도 있다. 

 

1 + 2 + 3 + ... + 9 + 10의 합이 55라는 점을 알고 있으면 점화식을 대강 구해낼 수 있다. 더 효과적으로 구할 수 있게 1~3자리의 마지막이 2인 오르막 수만 구해보자.

 

2 # 1
02 12 22 # 1+2
002 012 022 112 122 222 # 1+2+3

손으로 실제로 써가면서 해보면 점화식을 구해낼 수 있다.

 

d[i][j] = sum(d[i-1][k]) # k는 0부터 i-1까지

이렇게까지 구해놓고 코드를 작성하지 못했던 것 같다.

 

import sys

MOD = 10007
n = int(sys.stdin.readline())
dp = [[0] * 10 for _ in range(n + 1)]

for i in range(10):
    dp[1][i] = 1

for i in range(2, n + 1):
    for j in range(10): 
        dp[i][j] = sum(dp[i - 1][k] for k in range(j + 1)) % MOD 

print(sum(dp[n]) % MOD)

 

위의 점화식대로 반복문 코드를 써주면 된다.