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

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

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

10844번: 쉬운 계단 수

이번 문제도 DP 문제이다.

 

처음에 생각했던 것과 코드로 작성한 것이 쪼끔 개념이 다르긴 한데, 전체적으로는 같다. 우선 계단 수에서 한 자릿수에 대하여 리스트에 저장해 놓았다. 그리고 리스트에 저장되어 있는 값은 현재 해당 인덱스가 마지막 수, 즉 1의 자리 수일 때 가능한 수의 개수이다.

 

음.. 한 자릿수일 때가 아닌 두 자리 수일 때를 풀이해보면 이해가 될 것 같다. 한 자리가 늘어나게 될 때 1의 자리 수가 0이 되기 위해서는 앞자리가 1일 수밖에 없다. 따라서 10 하나의 경우만이 존재하게 되고, stairs[0] = 1이 된다.

1의 자리 수가 1이 되기 위해서는 앞자리가 0 또는 2가 되어야 한다. 0으로 시작하는 두 자리 숫자는 없지만 어차피 개수가 0이기 때문에 더해주면 stairs[0] + stairs[1] = 1 이 되어 1가지가 존재하게 되고, 21이 그 값이다.

1의 자리 수가 2가 되기 위해서는 앞자리가 1 또는 3이 되어야 한다. 따라서 가능한 두 자리 숫자는 stairs[1] + stairs[3] = 2가 되어 두 가지 경우가 존재하며 12와 32가 그 값들이다.

이러한 방식으로 이어나가게 되면 두 자릿수일 때 리스트는 [1, 1, 2, 2, 2, 2, 2, 2, 2, 1]가 된다.

 

마찬가지 방식으로 자릿수를 늘려나가면 된다.

 

코드에서는 위처럼 생각해서 작성을 했고 처음에 생각했을 때에는 old_stairs[i]의 값을 new_stairs[i-1], new_stairs[i+1]에 더해주려 했다.

 

import sys

N = int(sys.stdin.readline())
stairs = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
mod = 1000000000

for _ in range(1, N):
    tmp = stairs[:]
    stairs[0] = tmp[1] % mod
    for i in range(1, 9):
        stairs[i] = (tmp[i-1] + tmp[i+1]) % mod
    stairs[9] = tmp[8] % mod

sys.stdout.write(str(sum(stairs) % mod))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다