백준 / 10844번 / 쉬운 계단 수 / python 파이썬

 

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

 

 

 

 

 

 

---

나의 풀이

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

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

 

이 문제는 인접한 수의 차이가 1인 수를 계단수라고 하고, 길이가 N인 계단 수의 개수를 구하는 문제로, DP를 사용하여 풀 수 있습니다.

dp[i][j]를 길이가 i, 마지막 숫자가 j인 계산 수의 개수로 정의하면, 계단 수 조건을 만족하기 위해 이전 자리에서 올 수 있는 숫자는 j+1, j-1이므로 점화식은 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]로 표현됩니다. 이때 j가 0 또는 9일 경우 각각 1, 8만 올 수 있습니다. 

 

초기값으로는 한 자리 계단 수인 1부터 9까지는 각 1개씩 존재하므로 dp[1][1]부터 dp[1][9]까지는 1로 초기화하고, 0은 시작 숫자가 될 수 없으므로 dp[1][0]은 제외합니다. 이후 길이가 2부터 N까지인 경우에 대해 점화식을 반복적으로 적용하면서 dp 테이블을 채워나갑니다. 마지막으로 길이가 N인 모든 계단 수의 개수는 문제 조건에 따라 1,000,000,000으로 나눈 나머지를 출력하여 구합니다.