[백준/파이썬Python] #10844 쉬운 계단 수 : 점화식이 생각이 안 날 때는 뒤를 잘라보자 ⛰️

⛰️ 문제

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

인접한 모든 자리의 차이가 1인 수를 계단 수라고 함
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하기
0으로 시작하는 수는 계단수가 아님

🧠 접근 방법

• 가장 뒤에 오는 수를 기준으로 개수를 찾음

입력

• N: 길이

• 1보다 크거나 같고, 100보다 작거나 같은 자연수

출력

• 정답을 1000000000으로 나눈 나머지

👩🏻‍💻 코드

for i in range(10):
    if i == 0:
        continue
    DP[1][i] = 1

길이가 1일 때의 초기값을 설정해줍니다.

for i in range(2, N+1):
    for j in range(10):
        # 앞에는 1밖에 올 수 없음
        if j == 0:
            DP[i][j] = DP[i-1][j+1]
        # 앞에는 8밖에 올 수 없음
        elif j == 9:
            DP[i][j] = DP[i-1][j-1]
        # 앞에 1 작은 것, 1 큰 것 두 가지가 올 수 있음
        else:
            DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]

루프를 돌면서 j가 0일 때(앞에는 1밖에 올 수 없습니다.), 9일 때(앞에는 8밖에 올 수 없습니다.), 1~8일 때(앞에 1 작은 수, 1 큰 수, 두 가지가 올 수 있습니다.)로 나눠서 점화식을 넣습니다.

📑 전체 코드

# 쉬운 계단 수
import sys
N = int(sys.stdin.readline())

DP = [[0]*10 for _ in range(N+1)]
for i in range(10):
    if i == 0:
        continue
    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][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[-1]) % 1000000000)