[백준]10844 쉬운계단수 #dp

1. 풀이

(N의 크기를 살펴보고 2차원이 가능하다면 2차원 dp를 떠올려보자..)

​

dp[i][j] : i자리수에서 j로 끝나는 계단 수의 개수

이때 i자리의 j로 끝나는 수는 i-1자리의 j-1로 끝나는수와 , j+1로 끝나는 수 끝에 j만 붙이면 되기때문에 두 경우의 수의 합으로 표현할 수 있다.

(단 j가 0이면 1을, 9이면 8만을 붙일 수 있는것을 주의)

​

따라서 아래와 같은 점화식을 만들 수 있다.

dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]

​

2. 소스코드

N=int(input())
dp=[[0 for j in range(10)] for i in range(N+1)]
for j in range(1,10):
    dp[1][j]=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])%1000000000

print(sum(dp[N])%1000000000)