[백준] 10844번 쉬운계단수 (Python)

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

10844번: 쉬운 계단 수

---

풀이과정

①문제 바라보기

DP문제인데 규칙을 발견해야한다고 생각했다. 0과 9의 경우 특별한 Case이기에 따로 분류해서 처리해야 한다.

 

②아이디어 펼치기

아래는 수형도이다.

N == 1일 경우, 0은 불가능하고 나머지 1~9는 모두 가짓수가 1개가 된다.

N == 2일 때 부터 규칙이 발견이 되는데 편의상 N이 3~4일 때로 예시를 들었다.

1. dp[4][0]으로 가기 위한 방법의 개수는 dp[3][1] 온전히 갖게 된다.
2. dp[4][9]으로 가기 위한 방법의 개수는 dp[3][8] 온전히 갖게 된다.
3. 나머지 경우에서는 모두 양쪽의 값, dp[N][j-1] + dp[N][j+1]을 갖게 된다. 

이 세가지 특성을 활용하여 코드를 작성하면 되는 것이다

 

③최종 코드

N = int(input())

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

for i in range(2,N+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1]

        elif j == 9:
            dp[i][j] = dp[i-1][8]

        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

print(sum(dp[N]))