[Python] 10844번 쉬운 계단 수

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

10844번: 쉬운 계단 수

---

 

22/09/22

 

 

전형적인 2차원 DP문제로, 그렇게 어렵진 않다.

 

푸는 유형만 알고 있다면 굉장히 쉽게 풀 수 있다.

---

 

문제 접근 방식:

 

 

비슷한 유형의 문제 중에서 오르막 수라는 문제가 있다.

 

이와 비슷하게 접근하면 되는데, 여기서 DP의 정의를 다음과 같이 정의하자.

 

DP[i][j] = 자리가 i자리 숫자일 때, 숫자가 j로 끝나는 계단 수의 개수

 

그러면 계단수의 정의 상, 바로 이전의 숫자가 1만큼만 차이가 나야 하므로,

 

 

• DP[i][0] = DP[i-1][1]
• DP[i][1] = DP[i-1][0] + DP[i-1][2]
• .....
• DP[i][9] = DP[i-1][8]

라는 관계가 성립한다.

 

이를 이용하여 그대로 구현하면 끝이다.

 

주의해야될 점은 숫자가 매우 커질 수 있으니 항상 모듈러 연산을 취해주어야 한다는 점이다.

---

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

# 10844번 쉬운 계단 수
# DP
'''
DP[i][j] = 자리가 i자리 숫자일 때, 숫자가 j로 끝나는 계단 수의 개수
DP[i][0] = DP[i-1][1]
DP[i][1] = DP[i-1][0] + DP[i-1][2]
...
DP[i][9] = DP[i-1][8]
'''


N = int(input())
DP = [[0 for _ in range(10)] for _ in range(N+1)]
DP[1][0] = 0
for i in range(1, 10):
    DP[1][i] = 1
for i in range(2, N+1):
    DP[i][0] = DP[i-1][1] % 1000000000
    for j in range(1, 9):
        DP[i][j] = (DP[i-1][j-1] + DP[i-1][j+1]) % 1000000000 
    DP[i][9] = DP[i-1][8] % 1000000000
print(sum(DP[N]) % 1000000000)