[Python] 11057번 오르막 수

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

11057번: 오르막 수

---

 

22/10/03

 

 

전형적인 DP문제로, 나는 이차원 배열을 사용하여 문제를 해결하였다.

---

 

문제 접근 방식:

 

 

나는 DP[i][j]의 정의를 다음과 같이 정의했다.

DP[i][j] = i자리 숫자일 때, j로 끝나는 오르막 수의 개수 

이와 같이 정의를 하면, j가 0일 때, 1일 때, ..., 9일 때 모두 비슷한 점화식을 가진다.

 

오르막 수의 정의 상 이전 숫자보다 항상 같거나 큰 숫자가 와야 하기 때문에, DP[i][0]의 경우의 점화식은 DP[i][0] = DP[i-1][0]이 나온다.

 

DP[i][1]의 경우는 DP[i-1][0] + DP[i-1][1]이 나온다.(0으로 끝나는 수에 1을 붙이는 방법의 수 + 1로 끝나는 수에 1을 붙이는 방법의 수)

 

마찬가지 방법으로, DP[i][9]의 경우는 DP[i-1][0]부터 DP[i-1][9]까지 모두 더한 것과 같다.

 

이를 그대로 코드로 구현하면 끝이다.

 

물론, 10007로 나눈다는 조건까지 고려하여 잘 구현해야 한다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11057번 오르막 수
# DP
'''
접근 방법:
수는 0으로 시작할 수 있으므로,
DP[i][j] = 자리가 i자리 숫자일 때, 숫자가 j로 끝나는 오르막 수의 개수
DP[i][0] = DP[i-1][0]
DP[i][1] = DP[i-1][0] + DP[i-1][1]
...
DP[i][9] = DP[i-1][0] + DP[i-1][1] + ... + DP[i-1][8] + DP[i-1][9]
'''
N = int(input())
DP = [[0 for _ in range(10)] for _ in range(N+1)]
for i in range(10):
    DP[1][i] = 1
for i in range(2, N+1):
    for j in range(10):
        DP[i][j] = sum(DP[i-1][:j+1]) % 10007
print(sum(DP[N]) % 10007)