[Python] 백준 11057번: 오르막 수 풀이

 

 

소스코드

n = int(input())
# dp 초기화 (최소 1개는 있으므로)
#dp[i][j] 에서 i는 자리수, j는 끝에 오는 수
dp = [[0]*10 for _ in range(n+1)]
dp[1] = [1]*10
for i in range (1, n+1):
    for j in range (0, 10):
        for k in range (0, j+1):
            dp[i][j] += dp[i-1][k]
print(sum(dp[n]) % 10007)

 

저번 문제와 마찬가지로 자리수에 따른 끝 자리 숫자로 규칙을 유추하였다.

 

1자리 일 때는 당연히 모든 숫자가 1가지 방법을 가진다. (0도 숫자 첫번째에 올 수 있음)

2자리 일 때는 _0 은 1개, _1은 2개, _2는 3개, ...._9는 10개를 가진다.

3자리 일 때는 __0은 앞에 _00이 되어야 하므로 _0갯수와 동일하게 1

__1은 앞에 _0 또는 _1이 와야하므로 dp[2][0] + dp[2][1] = 3

__2 는 앞에 _0, _1, _2 가 와야하므로 dp[2][0] + dp[2][1] + dp[2][2] = 6 이다. 

즉 dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j] 임을 알 수 있다.