[백준] 11057번: 오르막 수 (파이썬)

✅문제: 11057번

📌문제풀이

0부터 9까지의 숫자로 이루어진 오르막 수의 개수를 계산하는 문제임. 오르막 수는 각 자릿수가 이전 자릿수 이상인 수를 의미하며, n자리 오르막 수의 개수를 동적 계획법(DP)을 사용하여 계산함.

1. DP 배열 초기화
   • dp[i][j]: i자리 오르막 수 중 마지막 숫자가 j인 경우의 수를 저장하는 배열.
   • 초기값: dp[1][j] = 1: 한 자리 수는 0부터 9까지 각각 1개임.
2. 점화식
   • dp[i][j]: i자리 오르막 수에서 마지막 자릿수가 j인 경우를 구하기 위해, 이전 자릿수에서 0부터 j까지의 값을 더함.
     • dp[i][j] = dp[i−1][0] + dp[i−1][1] + ⋯ + dp[i−1][j]
3. 결과 계산
   • 모든 계산은 10007로 나눈 나머지를 저장함.
   • n자리 오르막 수의 총 개수는 dp[n][0] + dp[n][1] + ⋯ + dp[n][9]의 합임.

dp = [[0 for _ in range(10)] for _ in range(1001)]

for i in range(10):
    dp[1][i] = 1

for j in range(2, 1001):
    for i in range(10):
        for k in range(i + 1):
            dp[j][i] += dp[j - 1][k] % 10007

n = int(input())
result = sum(dp[n]) % 10007
print(result)

📌후기

• DP 배열과 점화식을 활용해 문제를 해결하는 문제로 다이나믹 프로그래밍 연습하기 좋은 문제였던 것 같음.