[백준/DP] 15990 1, 2, 3 더하기 5 (Python, 파이썬)

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

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

 

 

문제의 조건

- 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제

- 단 같은 수를 두 번 이상 연속해서 사용하면 안된다.

- n=4

- 1+2+1

- 1+3

- 3+1

 

* 조건 때문에 점화식을 그대로 사용할 수 없다. -> 그 조건을 점화식에 넣기

 

D[i][j] = i를 1, 2, 3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j

 

... + 1 = i   -> D[i][1] = D[i-1][2] + D[i-1][3]

... + 2 = i  -> D[i][2] = D[i-2][1] + D[i-2][3](

... + 3 = i  -> D[i][3] = D[i-3][1] + D[i-3][2]

 

그러므로 정답은 D[n][1] + D[n][2] + D[n][3]이다.

 

* 예외처리

- D[1][1] = 1

- D[2][2] = 1

- D[3][3] = 1

 

 

limit = 100000 # n은 양수이며 100,000 보다 작거나 같다.
mod = 1000000009 # 나눈 나머지를 구하기 위해
d = [[0] * 4 for _ in range(limit+1)] # 인덱스는 0이 아닌 1부터 시작

for i in range(1, limit+1):
    if i-1 >= 0: # 1을 마지막 수로 사용했을 경우
        d[i][1] = d[i-1][2] + d[i-1][3] # 다음에 사용할 수는 2 또는 3
        if i == 1:
            d[i][1] = 1 # 같은 수를 사용하는 경우는 한가지
    
    if i-2 >= 0: # 2를 마지막 수로 사용했을 경우 
        d[i][2] = d[i-2][1] + d[i-2][3] # 다음에 사용할 수는 1 또는 3
        if i == 2:
            d[i][2] = 1 # 같은 수를 사용하는 경우는 한가지
    
    if i-3 >= 0: # 3을 마지막 수로 사용했을 경우
        d[i][3] = d[i-3][1] + d[i-3][2] # 다음에 사용할 수는 1 또는 2
        if i == 3:
            d[i][3] = 1 # 같은 수를 사용하는 경우는 한가지
    
    # mod 로 나눈 나머지를 저장
    d[i][1] %= mod
    d[i][2] %= mod
    d[i][3] %= mod

t = int(input())

for _ in range(t):
    n = int(input())
    print(sum(d[n])%mod)