백준 - 10844. 쉬운 계단 수

[백준] 10844. 쉬운 계단 수

Link

문제

45656이란 수를 보자.

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

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

입력

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

(N은 주어진 수의 자리 수를 의미한다.)

출력

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

풀이

N의 자리수를 가진 수가 계단수를 가지는 경우의 수를 구하는 문제이다.

예를들어 N이 2라면 10 ~ 99 사이 계단수의 개수를 구해보면 아래와 같이 총 17개의 경우가 나온다.

10	12
21	23
32	34
43	45
54	56
65	67
76	78
87	89
98	x

​

101	121	123
212	210	232	234
321	323	343	345
432	434	454	456
543	545	565	567
654	656	676	678
765	767	787	789
876	878	898
987	989

이를 바탕으로 유추한 규칙은 대강 아래와 같다.

• N자리의 숫자가 0이면 (N+1)자리의 숫자는 1밖에 올 수 없다 -> 경우의 수 1개
• N자리의 숫자가 9이면 (N+1)자리의 숫자는 8밖에 올 수 없다 -> 경우의 수 1개
• 위를 제외한 나머지 경우는 N자리의 숫자가 k라면 k+1, k-1이 올 수 있다 -> 경우의 수 2개

예를들어 N=2일 때 (N-1)자리의 숫자가 2라면 (21, 23)의 경우가 있다.

N=3이고 (N-2)자리의 숫자가 2일 경우에는 (212, 210, 232, 234)의 경우가 생긴다.

자리수 N의 상승하고 결국 (N-2)자리의 숫자가 2라면, (N-1)자리의 숫자가 1또는3 일 때의 경우의 수를 합한 것이 된다.

예외사항) (N-1)의 자리수가 0이라면 N의 자리수가 1, (N-1)의 자리수가 9라면 N의 자리수가 8인 경우만을 계산한다.

• 자리수 표기: 123 -> N자리 = 1, (N-1)자리 = 2, (N-2)자리 = 3

• 10 -> 1 01
• 21 -> 2 10, 2 12
• 23 -> 2 32, 2 34
• 89 -> 8 98

이를 수식으로 표현하면 아래와 같다.

\[Cases[N][2] = Cases[N-1][1] + Cases[N-1][3] \\ Cases[N][0] = Cases[N-1][1] \\ Cases[N][9] = Cases[N-1][8]\]

자리수 N을 층 또는 시간의 개념으로 바라본다면, 결국 이 문제는 과거에 구해논 값을 가지고 현재의 값을 결정하는 동적 프로그래밍 (Dynamic Programming) 문제라고 해석할 수 있다. (동적프로그래밍: 어떤 큰 문제를 풀기위해 그 문제를 더 작은 문제로 나누어서 푸는 기법)

그러면 이제 위에서 유추한 규칙과 동적 프로그래밍 패러다임을 적용하여 코드를 작성해보자

N = int(input())  # Take input
table = [[0] * 10 for _ in range(N)]

table[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] # 먼저 N=1 일 때의 경우를 예외처리
# 위 수식 참고
for jary in range(1, N):
    # 0과 9일 때의 예외처리
    table[jary][0] = table[jary-1][1]
    table[jary][9] = table[jary-1][8]

    for namuji in range(1, 9):
        table[jary][namuji] = table[jary-1][namuji-1] + table[jary-1][namuji+1]

print(sum(table[N-1]) % 1000000000)