백준 15990 - 1, 2, 3 더하기 5 [파이썬]

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

15990번: 1, 2, 3 더하기 5

 

풀이 과정

 

https://greentea31.tistory.com/28

백준 9095 - 1, 2, 3 더하기 [파이썬]

 

위의 문제에서 같은 수를 2번 연속으로 사용하면 안된다는 조건만 추가되었다.

 

D[n][k] => 정수 n을 마지막이 k로 끝나게끔 합으로 나타내는 경우의 수라고 하자.

그렇다면 k에 따라 점화식을 달리 해서 같은 수가 2번 연속으로 나타나지 않도록 조정이 가능하다.

 

D[n][1] = D[n-1][2] + D[n-1][3]

D[n][2] = D[n-2][1] + D[n-2][3]

D[n][3] + D[n-3][1] + D[n-3][2]

 

소스 코드

import sys

T = int(sys.stdin.readline())
d = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0], [0, 1, 1, 1]]
for i in range(4, 100001):
    d.append([0, (d[i-1][2] + d[i-1][3]) % 1000000009, (d[i-2][1] + d[i-2][3]) % 1000000009, (d[i-3][1] + d[i-3][2]) % 1000000009])
for _ in range(T):
    n = int(sys.stdin.readline())
    print(sum(d[n]) % 1000000009)