[BOJ] 11058 / 오르막 수 / Python

[BOJ] 11058 / 오르막 수 / Python

[BOJ] 11058 / 오르막 수 / Python

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

11057번: 오르막 수

 

풀이

BOJ / 10844 / 쉬운 계단 수 와 유사한 문제이다.

쉬운 계단 수 문제와 마찬가지로, 경우의 수를 이차원 배열로 정리하여 결과에 대한 연관성을 구하였다.

		0     1     2     3     4     5     6     7     8     9
N = 1 ->	1     1     1     1     1     1     1     1     1     1
		      ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓
N = 2 ->	1  →  2  →  3  →  4  →  5  →  6  →  7  →  8  →  9  → 10
		      ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓
N = 3 ->	1  →  3  →  6  → 10  → 15  → 21  → 28  → 36  → 45  → 55
		      ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓     ↓
N = 4 ->	1  →  4  → 10  → 20  → 35  → 56  → 84 → 120 → 165 → 220

 

이차원 배열을 이용한 점화식은, dp[i][j] = dp[i][j-1] + dp[i-1][j] 가 된다.

 

N = int(input())

dp = [ [0 for _ in range(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][0] = 1
    for j in range(1, 10):
        dp[i][j] = dp[i][j-1] + dp[i-1][j]
            
print(sum(dp[N]) % 10007)