[BOJ] 쉬운 계단 수 (no.10844)

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

🤔 생각

• 순회 중인 수에 대한 정보를 저장하고 있어야 한다.
• 따라서 dp 배열을 2차원으로 구성해야겠다.

메모이제이션

dp[i][j] : 길이가 i이고 순회 중인 수가 j일 때 계단수 갯수

케이스

1. 이전 수보다 1 작게
2. 이전 수보다 1 크게

+) 0,9 등 극단값은 따로 조건문으로 처리

🔥 점화식
dp[i] = dp[i-1][j-1] + dp[i-1][j+1]

📌 내 풀이

import sys
input = sys.stdin.readline

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

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

✔ 회고

• 2차원 배열을 사용한 DP를 복습할 수 있었다.