문제 : https://www.acmicpc.net/problem/10844
💻 Code
n = int(input())
dp = [[0 for _ in range(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])%1000000000)이 문제는 점화식을 생각하는게 정말 어렵다.
🔖 N=3 일 때 DP 테이블
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 1자리수 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2자리수 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
| 3자리수 | 1 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 3 | 2 |
- 첫 줄 : 0 1 2 3 4 5 6 7 8 9 -> 맨 뒤에 올 수 있는 숫자
ex) 2자리수 일 때
- 맨 뒤에 0이 오는 경우 : 10 (1개)
- 맨 뒤에 1이 오는 경우 : 21 (1개)
- 맨 뒤에 2가 오는 경우 : 12, 32 (2개)
- 맨 뒤에 9가 오는 경우 : 89 (1개)
-> 표를 통해 해당 위치의 값은 대각선 위 위치의 숫자들의 합과 같다는 것을 알 수 있다!
i : 행, j : 열 이라 할 때 점화식은
j=0,dp[i][j] = dp[i-1][1]
j=9,dp[i][j] = dp[i-1][8]
else,dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
이거를 생각해서 푼다는게 말이 안 된다. 그냥 외우자
