#154 백준 파이썬 [10844] 쉬운 계단 수

https://www.acmicpc.net/problem/10844

 

#Solution

정답 비율이 저렇게 낮은 이유를 잘 모르겠다. 다음과 같은 로직이다.

 

1) 0~9로 시작하는 숫자 * 100번째 자리 까지 리스트를 만들어준다.

2) n번째 k로 시작하는 계단수는 n-1번째의 k-1, k+1번째로 시작하는 계단수를 더해준 값

3) 단지 0으로 시작하는 것은 n-1의 1로 시작하는 계단수, 9로 시작하는 것은 n-1의 8로 시작하는 계단수만 더해주면 된다.

4) 0으로 시작하는 숫자는 없다고 해주었으므로 stair_numbers[N]의 1부터 9까지의 숫자만 더해서 출력해준다.

stair_numbers = [[0 for _ in range(10)] for _ in range(101)]

for i in range(1, 101):
    for j in range(10):
        if i == 1:
            stair_numbers[i][j] = 1
        else:
            if 1 <= j <= 8:
                stair_numbers[i][j] = stair_numbers[i-1][j-1] + stair_numbers[i-1][j+1]
            elif j == 0:
                stair_numbers[i][j] = stair_numbers[i-1][j+1]
            elif j == 9:
                stair_numbers[i][j] = stair_numbers[i-1][j-11]
                
N = int(input())             
print(sum(stair_numbers[N][1:10]) % 1000000000)