[백준] 10844번 쉬운 계단 수

 

DP 문제가 익숙해질 때까지 난이도를 올려가면 문제를 풀어보려고 합니다.

해당 문제는 규칙성을 찾았다고 생각했는데 올바른 접근법이 아니여서 시간이 걸렸습니다.

 

시도

- 안 되는 경우의 수를 찾기

- 전체 경우의 수 - 안되는 경우의 수

→ 안 되는 경우의 수가 1,2,3,6,10..... 나름의 규칙성을 가졌다고 생각해서 접근법을 가졌다고 생각했으나 틀렸다.

 

 

올바른 접근법

- 각 자리에 대한 경우를 쪼개서 생각

- 자리수가 늘어날때마다 각 숫자의 경우의 수를 생각하여 합하여 값 산출

- 일반적 경우 : 2~8은 다음 자리에 올 수 있는 경우가 2가지(이전 자리의 단계수의 경우의 수)

- 특수한 경우 : 0,9는 연속된 숫자가 1개임으로 각각 1가지 경우만 존재

- dp를 2차원 배열로 만든다( n자리수, n 자리에 올 수 있는 경우의 수)

-> 자리수가 늘어날 때마다 각 숫자에 올 수 있는 이전 자리의 경우의 수를 더해준다

    ex) ?3 →23,43의 각 경우의 수를 더해준다 , ?9 → 89의 경우의 수만 해당

 

n = int(input())

dp = [[ 0 for _ in range(10)] for _ in range(n)]
dp[0] = [0] + [1]*9 

for i in range(1,n):
    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-1])%1000000000)