[Python] 오르막 수 - 백준 (DP)

해당 글은 백준 11057번 문제 '오르막 수'을 다룬다.

문제

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

11057번: 오르막 수

 

설명

해당 문제는 DP로 간단하게 풀 수 있는 문제이다.

먼저 수는 0부터 시작할 수 있고, 인접한 수가 같아도 오름차순으로 친다는 조건이 있다.

한 자리의 수는 모든 값이 오르막 수 이므로 0~9까지의 1의 자리수를 의미하는 dp 배열을 [1]*10으로 초기화해준다.

두 자리의 수는 이전의 한 자리의 수의 dp 배열을 활용해서 현재 자리수까지의 합을 누적해주면 된다.

즉, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] → [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] → [1, 3, 6, 10, 15, 21, 28, 36, 45, 55] → .. 가 반복된다.

이때 dp 배열의 모든 값의 합이 갯수가 오르막 수의 갯수가 된다.

6개월 전에 풀었던 문제인데, 의외로 해당 코드를 열람한 사람이 꽤 있어서 기록해둔다..!

 

코드

n = int(input())
dp = [1]*10

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