[파이썬(Python)] 백준 10844번 쉬운 계단 수

 

 

백준 10844번: 쉬운 계단 수

문제 바로 가기

---

📌 문제

45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다.
이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

 

 

 

 

 

📝 아이디어

 

이 문제는 계단 수의 개수를 구하는 문제입니다. 계단 수란 각 자리의 숫자 차이가 1인 수를 말합니다. 예를 들어, 숫자 45656은 다음과 같이 자릿수의 차이가 모두 1이므로 계단 수입니다.

$$4 \xrightarrow{+1} 5 \xrightarrow{+1} 6 \xrightarrow{-1} 5 \xrightarrow{+1} 6$$ 

 

 

첫 번째 자리 숫자는 0으로 시작할 수 없습니다. 따라서 첫 번째 자리는 숫자 1 ~ 9까지 가능합니다.

 

현재 숫자가 $x$라면 다음 자리 숫자는 $x - 1$ 또는 $x + 1$이어야 합니다. 예를 들어 $x = 3$이면 다음 숫자는 2 또는 4만 가능합니다. $x = 0$이라면 다음 숫자는 1만 가능합니다. $x = 9$라면 다음 숫자는 8만 가능합니다.

 

 

동적 프로그래밍(DP)을 사용하여 계단 수를 구합니다. 각 자리의 숫자에 따라 가능한 다음 숫자를 계산하고 이를 누적해가며 길이가 $N$인 계단 수를 구합니다.

 

 

1. DP 테이블 정의

$dp[i][j]$는 길이가 $i$인 계단 수 중에서 마지막 숫자가 $j$인 경우의 수입니다. 

 

 

2. 점화식 도출

계단 수의 정의에 따르면 각 자리의 숫자 $j$는 이전 자리 숫자에서 1 증가하거나 1 감소해야 합니다. 즉, 현재 숫자 $j$는 이전 자리에서 $j-1$ 또는 $j+1$에서 올 수 있습니다. 이를 바탕으로 길이가 $i$인 계단 수를 구할 때 마지막 숫자가 $j$인 경우는 다음과 같습니다.

 

$$dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]$$

 

숫자는 0부터 9 사이에 있어야 합니다. 따라서 $j-1$ 또는 $j+1$이 범위를 벗어나면 그 경우는 고려하지 않아야 합니다. 

 

 

 

 

 

👩‍💻 나의 답안

MOD = 1000000000

N = int(input())

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

for j in range(1, 10):
    dp[1][j] = 1

for i in range(2, N + 1):
    for j in range(10):
        if j - 1 >= 0:
            dp[i][j] += dp[i - 1][j - 1]
        if j + 1 <= 9:
            dp[i][j] += dp[i - 1][j + 1]
        dp[i][j] %= MOD

result = sum(dp[N]) % MOD
print(result)