BOJ-10844 쉬운 계단 수

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

문제 소개

인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다. n이 주어졌을 때, 길이가 n인 계단 수의 개수를 구한다.

문제 풀이

리스트 last와 t를 통해 DP로 풀이하였다. t는 DP과정 중 임시로 값을 담는 리스트이다.

리스트 last의 각 인덱스는 각 숫자로 끝나는 계단 수의 개수를 의미한다. last는 처음에 n이 1인 경우로 초기화되고, 반복문을 통해 n이 1씩 커질 때마다 누적되는 값으로 업데이트한다.

마지막 숫자가 0인 경우와 9인 경우는 그 외의 경우와는 다르게 처리한다. 0은 1의 다음 수로만 가능하며, 9는 8의 다음 수로만 가능하기 때문이다.

결과는 sum(last) % 1000000000으로 출력한다.

코드

n = int(input())

last = [0] + [1] * 9
t = last.copy()

for k in range(n - 1):
    t = last.copy()
    for i in range(10):
        if i == 0:
            last[i] = t[i + 1]
        elif i == 9:
            last[i] = t[i - 1]
        else:
            last[i] = t[i - 1] + t[i + 1]

print(sum(last) % 1000000000)