[Python]15990. 1,2,3 더하기 5

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

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

---

 

1차원의 DP로 풀 수 있긴 한데.. 시간이 매우매우 많이 걸린다..!!

문제 조건에 따르면 끝 자리 수와 비교하여 다를때만 연산을 해줘야 하기 때문.

따라서 2차원 DP 를 이용해서 조건을 쪼개본다.

 

DP[i][1] = DP[i - 1][2] + DP[i - 1][3] # 현재 1은 1단계 전의 2 또는 3 에 붙을 수 있다. 
DP[i][2] = DP[i - 2][1] + DP[i - 2][3] # 현재 2은 2단계 전의 1 또는 3 에 붙을 수 있다.
DP[i][3] = DP[i - 3][1] + DP[i - 3][2] # 현재 3은 3단계 전의 1 또는 2 에 붙을 수 있다.

 

단, DP[1], DP[2], DP[3] 은 위 점화식을 따르지 않는다.

이유는 1, 2, 3 을 사용하여 덧셈을 나타내므로 위 규칙이 일반적으로 적용되지 않는다. 따라서, 별도의 예외처리를 해줘야 한다.

MAX = 100000
mod = 1000000009
DP = [[0]*(3+1) for _ in range(MAX+1)]

for i in range(1, MAX + 1):
    if i-1 >= 0:
        DP[i][1] = (DP[i - 1][2] + DP[i - 1][3]) % mod
        if i == 1:
            DP[i][1] = 1

    if i - 2 >= 0:
        DP[i][2] = (DP[i - 2][1] + DP[i - 2][3]) % mod
        if i == 2:
            DP[i][2] = 1

    if i - 3 >= 0:
        DP[i][3] = (DP[i - 3][1] + DP[i - 3][2]) % mod
        if i == 3:
            DP[i][3] = 1

for _ in range(int(input())):
    N = int(input())
    print(sum(DP[N]) % mod)

 

 

별도의 예외처리 없이 DP[1]~DP[3]까지 미리 초기화하여 사용하면 코드가 더 간편해진다.

 

MAX = 100000
mod = 1000000009
DP = [[0]*(3+1) for _ in range(MAX+1)]

DP[0] = [0, 0, 0, 0]
DP[1] = [0, 1, 0, 0]
DP[2] = [0, 0, 1, 0]
DP[3] = [0, 1, 1, 1]

for i in range(4, MAX + 1):
    DP[i][1] = (DP[i - 1][2] + DP[i - 1][3]) % mod
    DP[i][2] = (DP[i - 2][1] + DP[i - 2][3]) % mod
    DP[i][3] = (DP[i - 3][1] + DP[i - 3][2]) % mod

for _ in range(int(input())):
    N = int(input())
    print(sum(DP[N])% mod)

'''
DP[0] = [0, 0, 0, 0]
DP[1] = [0, 1, 0, 0]
DP[2] = [0, 0, 1, 0]
DP[3] = [0, 1, 1, 1]
DP[4] = [0, 2, 0, 1]
DP[5] = [0, 1, 2, 1]
DP[6] = [0, 3, 3, 2]
'''