스테핑 넘버(Stepping Number)란 인접한 모든 자릿수 사이의 절대적인 차이가 정확히 1인 수를 의미합니다. 예를 들어 123은 각 자릿수의 차이가 1씩 나므로 스테핑 넘버에 해당하지만, 124는 2와 4의 차이가 2이므로 스테핑 넘버가 아닙니다.
문제 정의
숫자 n이 주어졌을 때, n자리 스테핑 넘버의 총 개수를 구하는 프로그램을 작성해야 합니다. 결과값이 매우 커질 수 있으므로 10^9 + 7로 나눈 나머지를 반환하도록 합니다.
예를 들어 입력이 n = 2일 때 출력은 17입니다. 두 자리 스테핑 넘버는 다음과 같이 총 17개가 존재합니다.
[12, 23, 34, 45, 56, 67, 78, 89, 98, 87, 76, 65, 54, 43, 32, 21, 10]
풀이 접근 방법: 동적 계획법(DP)
이 문제는 동적 계획법을 활용해 효율적으로 해결할 수 있습니다. 핵심 아이디어는 dp[d]를 "현재 길이에서 마지막 자릿수가 d인 스테핑 넘버의 개수"로 정의하는 것입니다. 한 자릿수를 추가로 붙일 때 새 숫자의 끝자리가 d가 되려면 이전 숫자의 끝자리가 d-1 또는 d+1이어야 하므로, 이를 바탕으로 점화식을 세워 차례대로 갱신하면 됩니다.
알고리즘 단계
- 모듈러 값 m := 10^9 + 7로 설정
- n이 0이면 0을 반환
- n이 1이면 10을 반환 (한 자리 숫자 0~9는 모두 스테핑 넘버)
- dp := 크기가 10인 리스트를 값 1로 초기화
- (n - 1)번 반복:
- ndp := 크기가 10인 리스트를 값 0으로 초기화
- ndp[0] := dp[1]
- i를 1부터 8까지 반복하며 ndp[i] := dp[i-1] + dp[i+1] 계산
- ndp[9] := dp[8]
- dp := ndp로 갱신
- dp[1:]의 합을 m으로 나눈 나머지 반환 (n ≥ 2일 때 첫 자릿수는 0이 될 수 없으므로 인덱스 0 제외)
파이썬 구현 예시
class Solution:
def solve(self, n):
m = (10 ** 9 + 7)
if n == 0:
return 0
if n == 1:
return 10
dp = [1] * 10
for _ in range(n - 1):
ndp = [0] * 10
ndp[0] = dp[1]
for i in range(1, 9):
ndp[i] = dp[i - 1] + dp[i + 1]
ndp[9] = dp[8]
dp = ndp
return sum(dp[1:]) % m
ob = Solution()
n = 3
print(ob.solve(n))
실행 결과
입력:
3
출력:
32
n = 3일 때 세 자리 스테핑 넘버는 총 32개임을 확인할 수 있습니다.
시간 복잡도 분석
이 알고리즘은 각 자릿수 길이마다 크기 10짜리 배열을 한 번씩 갱신하므로 시간 복잡도는 O(n)이며, 고정된 크기의 배열 두 개만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 n이 매우 큰 경우에도 효율적으로 동작합니다.