📖 문제
https://www.acmicpc.net/problem/10844
💻 내 코드
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][j+1]
elif j==9:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=dp[i-1][j+1]+dp[i-1][j-1]
print(sum(dp[n])%1000000000)💡 풀이
- 다이나믹 프로그래밍 이용
- 규칙을 먼저 찾아보면
- 0은 맨 앞에 올 수 없음
- 한 자리 수 일 때: 1~0까지 1개씩 총 9개
- 두 자리 수 일 때:
- 맨 뒤의 숫자가 0이라면: 앞에 1만 올 수 있다(1개)- 맨 뒤의 숫자가 1이라면: 앞에 2만 올 수 있다(1개)
- 맨 뒤의 숫자가 2라면: 앞에 1, 3이 올 수 있다(2개)
...
- 이런 식으로 구해서 맨 뒤 숫자를 기준으로 올 수 있는 수의 개수를 구해보면 다음과 같다
| 자리수/맨 뒤 숫자 | 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은 오른쪽 위 숫자, 9는 왼쪽 위 숫자가 된다
- 이를 새로 생성한 리스트인 dp에 저장해서 case를 나누어서 구하면 된다
