백준 알고리즘 - 쉬운 계단 수 (10844) [Python]

 문제

 

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

 

 

 

 

 

 문제 상황

 

- 각자리 숫자의 차가 1씩 나는 수를 만들 때 자리수마다 만들 수 있는 수의 개수를 구한다.

 

 

 

 

 

 해결 전략

 

- N자리 숫자는 N-1자리 숫자의 끝에 숫자를 붙이는 구조인데, N-1자리의 1의 자리가 0 또는 9인 경우는 두가지가 아니라 1가지 숫자만 올 수 있다. 결국 number_(N) = number_(N-1) * 2 - (1의 자리가 0 또는 9인 경우의 수)가 된다. 이 때 1의 자리가 0 또는 9인 경우의 수는 N-2에서 1 또는 8의 개수가 된다.

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
div = 1000000000
N = int(input())
cache = [0, [0,1,1,1,1,1,1,1,1,1]] + [[0 for i in range(10)] for j in range(N-1)]
for i in range(2, N+1):
    for j in range(11):
        if j>0 and j<9:
            cache[i][j] = (cache[i-1][j-1] + cache[i-1][j+1])%div
        elif j == 0: cache[i][j] = cache[i-1][1]
        elif j == 9: cache[i][j] = cache[i-1][8]
print((sum(cache[N]))%div)

 

 

 

 

 

 해설

 

- 결국 포인트는 앞의 숫자는 다 필요없고 1의 자리 수만 관찰하면 된다는 사실이다. 처음에는 합 자체를 관찰하려고 햇으나 결국에는 1의 자리 수의 개수를 전부 저장하면 생각하기가 쉬운 문제였다.

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 문제의 조건을 보고 필요한 부분과 필요 없는 부분을 구별하여 생각할 수 있어야한다. 경우가 나누어져 있다면 꼭 전체로 계산할 필요가 없다.