[백준] 쉬운 계단 수

출처:: www.acmicpc.net/problem/10844

분류:: dp

 

1. 문제 이해 및 해결과정

- dp[i][j] = 길이가 i일때 , 끝자리가 j일 경우 계단 수의 개수 - 0은 계단수가 아니다       j        0 1 2 3 4 5 6 7 8 9     dp[1]    0 1 1 1 1 1 1 1 1 1     dp[2]    1 1 2 2 2 2 2 2 2 1    ex)dp[2][0] = 길이가 2일때, 끝자리가 0인 수의 개수 =>1개, 10     dp[3]    1 3 3 4 4 4 4 4 3 2    ex) dp[3][2] = 길이가 3일때, 끝자리가 2인 것의 개수 =>3개, 132 212 232 - dp[3][2] 를 보면, 끝자리가 2일 경우 가능한 앞자리는 1 과 3이다. 길이가 2이면서, 끝자리가 1과 3 인경우는 각각 1개(21) , 2개(43,23)이 있다.  1) 끝자리 0일 경우, 가능한 수는 1개, 1  =>dp[i][j]=dp[i-1][j+1] 2) 끝자리 1~8일경우, 가능한 수는 2개 n-1,n+1 => dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1] 3) 끝자리 9일 경우, 가능한 수는 1개, 8  => dp[i][j]=dp[i-1][j-1]

 

 

2. 풀이방법

  1. [python] dp

#쉬운 계단 수
#https://www.acmicpc.net/problem/10844
import sys
sys.stdin = open("input.txt","r")
n=int(input())
dp=[[0]*10 for _ in range(n+1)]
mod=1000000000 #저장과정에서 int값 초과할 수 있어서
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]%mod #범위초과 방지를 위해 중간과정에도 mod필요 
        elif j==9:
            dp[i][j]=dp[i-1][j-1]%mod
        else:
            dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]%mod

print(sum(dp[n])%mod)

 

3. 오답원인

 

4. 알게된 점