[Python, 10844번] 쉬운 계단 수

---

☑️ [Python, 백준/10844번] 쉬운 계단 수

1️⃣ 문제

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

2️⃣ 접근

 

문제에 나오는 계단 수는 '1, 2, 1'과 같이 +-1로 이루어진 수가 연속되는 수를 의미한다. 입력 값으로 N이 주어지면, N만큼의 길이를 가진 계단 수를 일정 수로 나누고 나머지를 출력하는 문제다.

 

해당 문제는 처음부터 DP로 접근했다. 그래서 문제에 있어서 정석적인 접근은 아닐 것 같다. 일단 DP 문제인 것을 알고 있었기 때문에 점화식을 찾기 위해서 집중했다. 예제 1과 예제 2를 보면서 직접 DP 테이블을 그리면서 어떻게 패턴을 만들 수 있을지 고민했다.

 

N이 1일 때, 0은 스스로 나타날 수 없으므로, 출력 값은 9를 가진다. -> ( 1, 2, 3, 4, 5, 6, 7, 8, 9 )

그러면 테이블에 조건을 다음과 같이 세울 수 있다.

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

 

그리고 위 사진에서처럼 길이 N을 생각해보면서 여러 계단수를 구해보면 다음과 같은 결과를 얻을 수 있다.

0 : +1

1~8 : +1, -1

9 : -1

 

결과를 통해 다음의 점화식을 구할 수 있었다.

    for i in range(2, num + 1):
        for j in range(0, 10):
            if j == 0:
                dp_table[i][j] = dp_table[i - 1][j + 1] 
            elif j >= 1 and j <= 8:
                dp_table[i][j] = dp_table[i - 1][j - 1] + dp_table[i - 1][j + 1]
            elif j == 9:
                dp_table[i][j] = dp_table[i - 1][j - 1]

 

정답은 DP 테이블의 모든 J값을 더하고 일정 수의 나머지 값을 출력해야 하기 때문에 아래의 전체 코드와 같이 처리했다.

3️⃣ 코드

import sys

def dp():
    dp_table = [[0] * 10 for _ in range(num + 1)]
    
    for i in range(1, 10):
        dp_table[1][i] = 1
    
    for i in range(2, num + 1):
        for j in range(0, 10):
            if j == 0:
                dp_table[i][j] = dp_table[i - 1][j + 1] 
            elif j >= 1 and j <= 8:
                dp_table[i][j] = dp_table[i - 1][j - 1] + dp_table[i - 1][j + 1]
            elif j == 9:
                dp_table[i][j] = dp_table[i - 1][j - 1]
                
    sum = 0    
    for n in dp_table[num]:
        sum = sum + n
    return sum % 1000000000;

if __name__ == "__main__":
    num = int(input())
    print(dp())