문제

백준 10884 쉬운 계단 수

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

풀이

처음 생각한 정신나간 답

N = int(input())

print(N*9 - (N-1))

쉬운 계단이라길래 넌센스 문제인 줄 알았다...

Combination 으로 다 구한 다음 아닌 걸 소거해 볼까도 생각해 봤지만 100개를 Combination 하면 시간복잡도가 엄청 커지기 때문에 관뒀다.
10개라면 시도해 봤을지도 모르겠다.

이 문제는 DP 문제인데 점화식을 세우는 과정이 좀 어려웠다.
$a_n = f(a_{n-1})$ 형식으로 DP테이블을 생각하기도 했고, 숫자만 나열되어 있어서 2차원으로 확장시켜 생각하지 못했다.

DP테이블을 a[N][K] 라고 두면 N은 자리수, K는 끝에 숫자이다.
기본적은 점화식은 다음과 같다.

이 식의 뜻은 N번째 자리수의 K로 끝나는 계단 수의 갯수는
그 전단계(N-1)의 끝자리(N번째에서 보면 끝에서 두번째 숫자)가 K+1, K-1인 경우의 합이라는 뜻이다.
계단수의 특성을 이용한 DP라고 볼 수 있다.

이 때 예외사항을 지정해 줘야 하는데 K 가 0 or 9인 경우이다.

0으로 끝나는 경우는 끝에서 두번째 숫자가 1이어야만 하므로

9로 끝나는 경우는 끝에서 두번째 숫자가 8이어야만 하므로

이다.

정리해서 적어보면 다음과 같다.

코드

N = int(input())

# DPtable 초기화
a = [[0] * 10 for _ in range(N)]

# 1층 초값 설정
a[0] = [0,1,1,1,1,1,1,1,1,1]

# 점화식 구현
for n in range(1,N):
    a[n][0] = a[n-1][1] # 끝자리가 0
    a[n][9] = a[n-1][8] # 끝자리가 9
    
    for k in range(1,9): # 끝자리가 1~8
        a[n][k] = a[n-1][k-1] + a[n-1][k+1]
        
print(sum(a[N-1])%1000000000) # 0부터 시작해서 N자리수는 N-1로 접근