[BOJ][python] 11057. 오르막 수

 

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

---

💡IDEA

동적계획법을 사용하는 문제이다.

규칙을 찾기 위해 N이 1, 2, 3인 경우를 생각해보자.

먼저 N=1인 경우, 오르막 수는 0~9까지 각 1개씩 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]으로 모두 10개이다.

N=2인 경우, 오르막 수는 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]으로 모두 55개이다.

N=3인 경우, 오르막 수는 [55, 45, 36, 28, 21, 15, 10, 6, 3, 1]으로 모두 220개이다.

잘 생각해보면, N에 상관없이 모든 9번째 수=1 이고, N인 경우에 8번째 수 = N인 경우에 9번째 수 + N-1인 경우에 8번째 수 처럼 계산되는 것을 알 수 있다. 9번째 수부터 0번째까지 뒤에서부터 dp를 구성해서 채운다.

오르막 수의 개수는 dp의 합을 구하여 10007로 나눈 값으로 출력한다.

 

📌CODE

N = int(input())
dp = [[0]*10 for _ in range(N+1)]

dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
for i in range(2, N+1):
    dp[i][9] = 1
    for j in range(8, -1, -1):
        dp[i][j] = dp[i-1][j] + dp[i][j+1]

print(sum(dp[N])%10007)