💡문제접근
- 단편적으로 규칙성을 찾아보았지만 눈에 띄는 규칙성이 없었다. 가능한 경우들을 하나하나 나열하면서 정리를 해봤는데 아래의 표와 같은 변화를 확인할 수 있었다. 표를 기반으로 코드를 작성할 수 있었다. DP문제는 규칙성을 빠르고 정확하게 찾아내는 것이 문제의 핵심인 것 같다.
| 숫자의 자릿수 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 결과 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 9 |
| 2 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 | 17 |
| 3 | 1 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 3 | 2 | 32 |
- 예를 들어 숫자의 자릿수가 3인 경우 마지막 자리에 위치하는 숫자가 5인 경우의 값은 숫자의 자릿수가 2인 경우 마지막 자리에 위치하는 숫자가 4인 경우와 숫자의 자릿수가 2인 경우 마지막 자리에 위치하는 숫자가 6인 경우의 합이 된다.
💡코드(메모리 : 31256KB, 시간 : 48ms)
import sys
input = sys.stdin.readline
N = int(input().strip())
dp = [[0] * 10 for _ in range(101)]
for i in range(1, 10):
dp[1][i] = 1
for a in range(2, N+1):
for b in range(10):
if b == 0:
dp[a][b] = dp[a-1][1]
elif b == 9:
dp[a][b] = dp[a-1][8]
else:
dp[a][b] = dp[a-1][b-1] + dp[a-1][b+1]
print(sum(dp[N]) % 1000000000)💡소요시간 : 41m
🐢