[DP] 10844 - 쉬운 계단 수 (실버 1) with Python

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

10844번: 쉬운 계단 수

주저리 주저리

이런 유형의 문제는 제발 꼭 풀어보자. 언젠간 크게 도움이 되는 것 같다.

문제는 짧지만 어렵게 내거나 처음 풀면 많이 당황 스러울 수 있는 문제인 듯 하다.

중요 표시

문제 해결

이런 케이스는 무조건 표를 만들어서 그려야 한다.

길이/ 끝숫자	0	1	2	3	4	5	6	7	8	9
1	x	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	3	4	4	4	4	4	3	2

가로가 끝 숫자 세로가 N이라고 해보자

규칙이 보이는가?

자세히 보면 일단 끝 숫자가 0일 때랑 9일 때가 많이 유별해 보인다

이들은 각각 자기 n-1대의 끝 숫자 1 or 8의 값을 그대로 갖는 것을 볼 수 있다. (그럴 수 밖에 없다.)

그럼 다른 것들은 어떤가

이들은 두가지의 경우가 생긴다.

자기보다 작은 값으로 갈 것인가 큰 값으로 갈 것인가라는 두가지 선택지가 생긴다

이를 식으로 쓰면

dp[i][j] = dp[i-1][j-1] + d[[i-1][j+1]이 된다.

이제 코드로 짜자

코드

import sys
n = int(sys.stdin.readline())
mod = 1000000000
dp = [[0 for _ in range(10)] for _ in range(n+1)]
for i in range(9):
    dp[1][i+1] = 1
for i in range(2,n+1):
    for j in range(10):
        if j==0:
            dp[i][j] = dp[i-1][1]
            continue
        if j==9:
            dp[i][j] = dp[i-1][8]
            continue
        dp[i][j] = (dp[i-1][j-1]+dp[i-1][j+1])%mod

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