백준10844 문제 보러가기

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력 1

1

예제 출력 1

9

예제 입력 2

2

예제 출력 2

17

문제 해결

규칙 찾기

사실 이틀 걸린 문제다.
처음에는 n = 1 일때, n = 2 일 때 등으로 기준을 나눠서 규칙을 찾으려고 했다.

n = 1
1, 2, 3, ... , 9 -> 9개
n = 2
12, 21, 23, 32, 34, ..., 98 -> 17개
n = 3
??

처음에는 (9-1) * 2 + 1 같은 식인줄 알았다.
1의 자리수가 0 또는 9일 때는 다음 단게에 하나만 만들 수 있기 때문에 처음에 점화식은 다음과 같은 줄 알았다.

dp[i] = (dp[i-1] (i-1)) 2 + i - 1

그런데 이렇게 코드를 짜니 이것은 틀린 답이었다.

그리고 하루로는 해결 못하고 자고 일어나서 다시 봤다.
그런데 n = 1에서 n = 2로 넘어갈 때, 그러니까 n이 증가할 수록 개수에 영향을 끼치는 것은 1의 자리 또는 맨 앞자리 수의 숫자에 따라 영향을 미친다고 생각을 했다.

처음에는 1의 자리 수에 따라 기준을 세웠다.
그런데 사실 규칙을 찾지 못했다.
그러면 맨 앞자리 수에 따라 기준을 세워서 규칙을 찾아 표를 그렸다.

일단 맨 앞자리 수가 0이면 개수에는 count 되지 않지만, 배열을 정하는데에 영향을 주어 작성을 했다.
표에서 화살표가 그러져있는 n=3 일 때를 보자.
n = 3일 때, 그리고 맨 앞자리 수가 1일 때를 보자.
121, 123, 101로 3개가 있는 것을 볼 수 있다.
이는 n = 2일 때, 맨 앞자리 수인 2 일 때, 그리고 맨 앞자리수가 0일 때의 수를 합친거나 다름 없다고 볼 수있다.
121, 123, 101은 (1)21, (1)23, (1)01 이기 때문에 n = 2의 배열에서 i-1 그리고 i+1일 때와 같다.
맨 앞자리 수가 0일 때 그리고, 9일 떄는 i-1 또는 i+1 를 하면 -1, 10이 되어 버리기 때문에 각각 1일 때, 8일 때만 가져온다.
따라서 코드는 다음과 같다.

n = int(input())

dp = [1] * 10
if n > 1 :
    for _ in range(n-1) :
        check = [0] * 10
        for i in range(10) :
            if i == 0 : # i가 0, 즉 맨 앞자리 수가 0이면 n 전 단계 i가 1인 개수에서 가져오기
                check[i] = dp[i+1]
            elif i == 9 : # i가 9, 즉 맨 앞자리 수가 0이면 n 전 단계 i가 8인 개수에서 가져오기
                check[i] = dp[i-1]
            else :
                check[i] = dp[i+1] + dp[i-1]
                
        dp = check
    
l = sum(dp)-dp[0] # 맨 앞자리 수가 0일 때는 count 하지 않기 때문에 빼고 계산

print(l%1000000000)```