[동적계획법/DP] 백준 11057 오르막 수 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

11057번: 오르막 수

 

 

 

2. 문제 풀이

 길이가 N인 오르막 수를 구하는 문제입니다.

 

2022.06.02 - [Algorithm] - [DP/동적계획법] 백준 1904 01타일 - 파이썬(Python)

 DP문제로, 백준 01타일과 비슷합니다. 길이가 i-1인 오르막 수에서, 맨 끝자리보다 같거나 큰 숫자를 덧붙여서 길이가 i인 오르막 수를 만듭니다.

 예를 들어 길이가 3이고 맨 끝자리가 2인 오르막 수 cache[3][2]는 cache[2][0] + cache[2][1] + cache[2][2]의 합으로 구할 수 있습니다.

 

 

 

3. 코드

# 입력
n = int(input())

# DP
cache = [[0] * 10 for _ in range(n+1)]
for i in range(10):
    cache[0][i] = 1

for i in range(1, n+1):
    for j in range(10):
        for k in range(j+1):
            cache[i][j] += (cache[i-1][k] % 10007)
print(cache[n][9] % 10007)