[BOJ] 10844. 쉬운 계단 수

Jimeaning·2023년 3월 25일

코딩테스트

목록 보기

24/143

Python3,DP

문제

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

키워드

주요 포인트

각 자릿수가 가질 수 있는 계단 수를 구한다.

따라서 각 자릿수 별로 따져 봐야 한다.
dp[자릿수][맨 뒤에 오는 숫자]

먼저 자릿수가 1인 계단수는 1~9 모두 1씩 갖는다. (0부터 시작하는 수는 계단수가 아니므로 제외)

(자릿수가 2 이상일 때)

1) dp[i][j]라 할 때 가장 뒤에 오는 숫자가 0이면, dp[자릿수-1][1]이 되어야 한다.
=> 0 앞에는 1만 올 수 있기 때문이다.

따라서, j == 0일 때: dp[i][j] = dp[i-1][1]

2) 마찬가지로 가장 뒤에 오는 숫자 == 9이면, dp[자릿수-1][8]이다.
=> 9 앞에는 8만 가능하기 때문이다.

따라서, j == 9일 때: dp[i][j] = dp[i-1][8]

3) 1~8까지의 숫자는 dp[자릿수-1][j-1] + dp[자릿수-1][j+1] 한 값이다.
=> 1~8까지는 +- 1 숫자들이 가능하기 때문이다.

j가 1~8이라면, dp[자릿수-1][j-1] + dp[자릿수-1][j+1]

이렇게 구하면 가질 수 있는 자릿수의 경우의 수가 모두 리스트에 들어간다.
ex) 자릿수가 2일 때, [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]
리스트에 있는 모든 값을 더하면 길이가 n인 계단수가 총 몇 개인지 나온다.

따라서 dp에 저장된 모든 값을 더하고 1000000000으로 나눈 나머지값을 출력한다.

최종 코드

(23.5.9 수정)

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

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][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

res = sum(dp[n]) % 1000000000
print(res)