백준 10844 쉬운계단수

쉬운 계단수 (백준 10844)

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

dp의 적용범위에 대하여 다시금 느낀것 같다…

일단 고민하다, 결국 미세하게 구현값이 틀려
다른 블로그의 아이디어를 보았다

0일 때는 1로만 갈 수 있으며,
9일 때는 8로만 갈 수 있다
그 외의 경우는 -1,+1 로 갈 수 있다는 점이 포인트

또한 dp를 2차원 배열로 잡아야 하는 점도 특징인듯하다
(dp[process -1][i+1]을 알아야 하기에)

Code

import sys

inp = sys.stdin.readline

n = int(inp().strip())

dp = [[0 for _ in range(10)]for _ in range(n)]

for i in range(1,10):
    dp[0][i] = 1

MOD = 1000000000

def func():
    sum = 0
    for process in range(1,n):
        for i in range(0,10):
            if i == 0:
                dp[process][i] = dp[process - 1][i+1]
            elif i == 9:
                dp[process][i] = dp[process - 1][i-1]
            else:
                dp[process][i] = dp[process - 1][i-1] + dp[process - 1][i+1]

    for i in range(0,10):
        sum += dp[n-1][i]

    return sum

print(func()%MOD)

해결 아이디어

1. dp[process][i] : 현재 진행단계(process)에서
   i가 가질 수 있는 계단수의 개수
2. i가 0 이라면, 1로만 갈 수 있으며
   이 경우, ‘분기’하지 않기에 이전단계와 같은 수를 가진다
3. i가 9라면, 8로만 갈 수 있기에
   ‘분기’하지 않으며 이전 단계와 같은 수를 가짐
4. 그외의 경우는, i는 i-1과 i+1로 갈 수 있기에
   이전 단계의 두 방향에서의 값을 더하여 가진다
5. 마지막에 dp[n-1]의 모든 합을 구한 후 반환하고
   MOD만큼 나누어준다(문제에 적혀있기에)