백준 - 쉬운계단수(10844번) (DP)

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

10844번: 쉬운 계단 수

 

 처음에 숫자를 일일히 써가면서 규칙을 찾는데 엄청 고생했는데 다음과 같이 풀이하는 방법이 더 효율적이다.

 

 위 표는 마지막 자리 숫자가 무엇일때 생성될수 있는 가지수를 적어놓은 것이다. 예를 들어 dp[2][1]은 21 이렇게 하나밖에 존재 하지 않고 dp[2][3]은 23,43 두개가 존재한다.

 위처럼 작성해 놓으니 규칙을 쉽게 발견할수 있는데 빨간 화살표처럼 왼쪽 오른쪽 대각선 원소의 합이다.

 

 생각해보면 당연한게 5가 맨 뒷자리에 오려면 앞에 4나 6이 와야 하기 때문에 4나 6이 오는 경우의 수를 모두 합해주면 해결되는 문제였다.

 

import sys

N=int(sys.stdin.readline())
dp = [[0 for i in range(10)] for j in range(101)]
for i in range(1,10):
    dp[1][i]=1
    
for i in range(2,N+1):
    for j in range(0,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 )