[백준] 10844번 쉬운 계단 수 - Python / 알고리즘 기초 1/2 - 다이나믹 프로그래밍 1

---

---

---

💡 문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

---

💭 접근

0을 제외한 모든 숫자는 앞에 올 수 있고, 1~8까지의 숫자는 뒤에 붙을 수 있는 숫자가 2가지(+1, -1)이다. 하지만 9의 경우엔 뒤에 붙을 수 있는 숫자가 1가지(8)밖에 없는 점을 주의해야한다. 0또한 붙을수 있는 숫자가 1가지(1)밖에 없다.

ex) 4
1 [0 1 1 1 1 1 1 1 1 1 1]
2 [1 1 2 2 2 2 2 2 2 2 1]
3 [1 3 3 4 4 4 4 4 4 3 2]
4 [3 4 7 7 8 8 8 8 7 6 3] ...


dp[4][0] = dp[3][1]
dp[4][i] = dp[3][i - 1] + dp[3][i + 1]
dp[4][9] = dp[3][8]
...

---

📒 코드

n = int(input())

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

for i in range(2, n + 1):
    dp[i][0] = dp[i - 1][1] # 끝자리 0
    dp[i][9] = dp[i - 1][8] # 끝자리 9
    
    for j in range(1,9): # 끝자리 1~8
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
        
print(sum(dp[n]) % 1000000000)

---

💭 후기

점화식을 세울 때 무작정 억지로 세우려고 하지말고 문제를 잘 이해하고 패턴을 보는 것이 굉장히 중요한 것 같다.

---

🔗 문제 출처

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

---