백준 10844 쉬운 계단수 - python

시간 날 때마다 알고리즘 문제를 풀고 있다. 그 말은 동물의 숲 게임을 할 시간을 쪼개서 알고리즘 공부를 하고 있고, 혼자 뻘짓 하면서 상당히 애를 먹었던 재미난 문제이다. (=오늘 동물의 숲에 공원 만들어주려고 했는데 ㅂㄷㅂㄷ) 나는 말하는 감자야 !

문제

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

풀이

맨 처음 시작하는 자리 수가 0이나 9가 아닌 경우 : 2를 예로 들면,

2로 시작하는 두 자리 계단 수는 21 / 23 이다 .

즉 계단 수의 정의 상, 2로 시작하는 세 자리 계단 수에서 마지막 세 번째 자리에 오는 수는 이번엔 1 이나 3과 연속된 수여야한다. => 0, 2 / 2 , 4

=> 2로 시작하는 세 자리 계단 수 : 210, 212, 232,234

즉 ‘2’ + 1로 시작하는 두 자리 계단 수 , ‘2’ + 3으로 시작하는 두 자리 계단 수 이므로 ,

해당 숫자 -1 / + 1 로 시작하는 현재 구해주고자 하는 자리 수 이전 계단 수 개수의 합이 된다.

맨 처음 시작하는 자리 수가 0이나 9인 경우 : (사실 0은 맨 처음 시작할 수 없지만, 다른 숫자를 계산하기 위해서 계속 같이 구해줘야 한다. )

9를 예로 들면, 9로 시작하는 두 자리 계단 수는 98 하나 뿐이다.

즉 계단 수의 정의 상, 9로 시작하는 세 자리 계단 수에서 마지막 세 번째 자리에 오는 수는 이번엔 8 과 연속된 수여야한다. => 7 , 9

=> 9로 시작하는 세 자리 계단 수 : 987,989

즉 ‘9’ + 8로 시작하는 두 자리 계단 수 이므로

해당 숫자 -1 로 시작하는 현재 구해주고자 하는 자리 수 이전 계단 수 개수의 합이 된다.

import sys
input=sys.stdin.readline

class ES:
    def read(self):
        self.n=int(input())
    
    def solve(self):
        cur=1
        if self.n==cur:
            print(9)
            return
        self.dp=[1,2,2,2,2,2,2,2,2,1] #0,1,2,3,4,5,6,7,8,9
        cur+=1
        while cur<self.n:
            cur+=1
            tmp=[]
            for i in range(10):
                if i==0 or i==9:
                    tmp.append(self.dp[1])
                else:
                    tmp.append(self.dp[i-1]+self.dp[i+1])
            self.dp=tmp
        print(sum(self.dp[1:])%1000000000)
        
es=ES()
es.read()
es.solve()