백준 - DP (#10844)

https://www.acmicpc.net/problem/10844
45656이란 수를 보자.
이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

Code

N = int(input())

prev_count = [0]+[1]*9
count = [0]*10

for i in range(N-1):
    for j in range(10):
        if j == 0:
            count[j] = prev_count[1]
        elif j == 9:
            count[j] = prev_count[8]
        else:
            count[j] = prev_count[j-1] + prev_count[j+1]
    
    prev_count = count[:]

print(sum(prev_count)%1000000000)

참고
count는 해당 index를 마지막 자리수로 가지는 계단 수의 갯수

prev_count = count[:] ( O )
prev_count = count ( X )
위의 두 코드 중 아래 코드 같은 경우에는 값이 할당되는 것이 아니라 메모리만 참고한다. 그리고 만약 count의 값을 바꾼다면 prev_count의 값도 바뀐다.
그렇기 때문에 여기에서는 위 코드와 같이 값을 넣어주도록 한다.
list와 같은 mutable 객체는 모두 위와 같은 방식이다.
mutable과 immutable 에서의 차이와 얕은 복사(shallow copy)와 깊은 복사(deep copy)의 차이에 주의하자.
https://wikidocs.net/16038