[백준] 11057 오르막 수 다이나믹 프로그래밍

다이나믹 프로그래밍 조걸

1. 최적 부분 구조 

- 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있습니다.

2. 중복되는 부분 문제

- 동일한 작은 문제를 반복적으로 해결해야 합니다.

 

** 다이나믹 프로그래밍 문제를 푸는 첫번째 단계는 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고 자 하는 부분 문제의 중복 여부를 확인해보자 **

 

 

다이나믹 프로그래밍 문제를 보텀업 방식으로 풀었다.

 

 

 

n의 값이 1부터 1000이므로 dp = [[0] * 10 for _ in range(1001)]

n의 값을 자리수라고 생각을 하였다 n이 4이면 천의 자리수

따라서 일의 자리는 모두 1로 초기화

2의 자리부터 따져주었다 

현재 자리수의 값보다 다음 자리 수의 값이 크거나 같게 삼중 for문을 써주었다

(3중 for문 말고 dp[i][j] = dp[i-1][j] + dp[i][j-1]를 해도 상관없을 것 같음)

# 오르막 수
n = int(input())

dp = [[0] * 10 for _ in range(1001)]
for i in range(10):
    dp[1][i] = 1

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


print(sum(dp[n]) % 10007)