문제 요약
길이가 N인 계단 수(인접한 자리수 차이가 1인 수)의 개수를 구한다.
- 0으로 시작하면 안 됨
- 정답은
1,000,000,000으로 나눈 나머지 출력 - 1 ≤ N ≤ 100
내가 시도했던 접근 1: 실제 수를 전부 만들어 저장하기 (시간 폭발)
처음에는 길이별로 가능한 숫자들을 직접 만들어서 dp[count]에 저장하는 방식으로 시도했다.
n = int(input())
dp = [[]] * 101
dp[0] = [0]
dp[1] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
if n != 1:
for count in range(2, n + 1):
for num in dp[count - 1]:
for i in range(0, 10):
if abs((num % 10) - i) == 1:
dp[count].append(10 * num + i)
print(len(dp[n]))
왜 오래 걸렸나?
길이가 늘수록 가능한 계단 수 개수는 매우 빠르게 증가한다.
실제로 숫자 자체를 리스트에 저장하면, N=3부터도 리스트가 빠르게 커지고(그리고 N=100은 사실상 불가능) 시간/메모리가 감당이 안 된다.
추가로 숨어있는 버그: dp = [[]] * 101
[[]] * 101은 서로 다른 101개 리스트를 만드는 게 아니라, 같은 리스트 객체를 101번 참조하는 형태다.
즉, dp[2].append(...)를 하면 dp[3], dp[4]도 같이 바뀌는 식의 문제가 생길 수 있다.
올바른 초기화는 보통 아래처럼 한다.
dp = [[] for _ in range(101)]
내가 시도했던 접근 2: “전체 개수” 점화식을 직접 만들기 (점화식이 틀림)
두 번째로는 전체 개수만을 갖고 점화식을 만들려고 했는데, 계단 수는 “마지막 자리 숫자”에 따라 다음 선택지가 달라져서 전체 개수만으로는 정확한 점화식을 세우기 어렵다.
이 문제의 핵심은 상태를 더 세분화해야 한다는 것이었다.
정답 아이디어: DP 상태를 “길이 + 마지막 자리”로 정의하기
DP 정의
dp[len][d] = 길이가 len이고 마지막 자리(끝자리)가 d인 계단 수의 개수
초기값
길이 1에서 가능한 수는 1~9 (0으로 시작 불가)
dp[1][1..9] = 1dp[1][0] = 0
점화식(전이)
마지막 자리가 d가 되려면, 이전 길이의 마지막 자리는 d-1 또는 d+1 이어야 한다.
dp[len][d] = dp[len-1][d-1] + dp[len-1][d+1]
단, 범위를 벗어나는 경우는 제외:
- d=0이면 이전은 1만 가능 →
dp[len][0] = dp[len-1][1] - d=9이면 이전은 8만 가능 →
dp[len][9] = dp[len-1][8]
정답:
sum(dp[N][0..9]) % 1_000_000_000
시간 복잡도는 O(N * 10)이라 N=100은 매우 여유롭다.
정답 코드
n = int(input())
MOD = 1_000_000_000
# dp[len][digit]
dp = [[0] * 10 for _ in range(n + 1)]
for d in range(1, 10):
dp[1][d] = 1
for length in range(2, n + 1):
dp[length][0] = dp[length - 1][1] % MOD
dp[length][9] = dp[length - 1][8] % MOD
for d in range(1, 9):
dp[length][d] = (dp[length - 1][d - 1] + dp[length - 1][d + 1]) % MOD
print(sum(dp[n]) % MOD)
이번 문제로 배운 점 (DP 접근법)
- “값(수)을 전부 만들기”는 대부분의 DP 문제에서 시간/메모리 한계를 바로 넘는다.
- DP는 상태(state)를 잘 잡는 게 핵심이다.
여기서는 “길이만”으로는 부족했고, 마지막 자리까지 포함해야 점화식이 성립했다. - 점화식을 만들 때는 “현재 상태가 되기 위한 이전 상태”를 역으로 생각하면 정리가 쉽다.
(끝자리 d → 이전 끝자리 d-1 또는 d+1)