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

문제

10844번: 쉬운 계단 수

---

풀이

import sys
input = sys.stdin.readline

n = int(input().rstrip())

d = [[0] * 10 for _ in range(n+1)]

for i in range(1, 10):
    d[1][i] = 1
    
for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            d[i][j] = d[i-1][1]
        elif j == 9:
            d[i][j] = d[i-1][8]
        else:
            d[i][j] = d[i-1][j-1] + d[i-1][j+1]
            
print(sum(d[n]) % 1000000000)

 

이해하는데 한참 걸렸다. 다른 사람 풀이를 참고했다.

아이디어

⭐️ d[i][j] = d[계단 길이][마지막 숫자]

 

• 계단의 수가 하나일 때 1 ~ 9로 dp 초기화 해준다.

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

 

 

• 나머지 자릿수의 경우 가장 뒤에 오는 숫자가 0이면 그 앞에 1만 올 수 있다.

if j == 0:
    d[i][j] = d[i-1][1]

 

10 (✅) 01 (❌) <- 0으로 시작하는 수는 계단수가 아니다.

 

• 가장 뒤에 오는 숫자가 9일 땐, 그 앞에 8만 올 수 있다.

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

 

89(✅)

 

• 나머지 경우는 +1, -1 가능

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

 

67(-1, ✅), 87(+1, ✅)

 

마지막엔 각 자릿수(n)의 경우의 수를 모두 합한 후, 문제에서 주어진 1000000000로 나누어 출력한다.

 

---

 

참고

https://wooono.tistory.com/642