1,2,3 더하기 5 15990번 백준

문제:www.acmicpc.net/problem/15990

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

처음에 이 문제를 접 했을 때 기존 더하기 문제와 같이 피보나치의 꼴처럼 이전의 값을 단순히 더해나가면 될 줄 알았다. 그래서 문제의 푸는 방향을 오로지 총 갯수의 상관관계만 봤는데 그렇게 접근하면 안됐다. 이 문제는 사실 RGB거리 문제와 유사한 문제라 볼 수 있다. 방향성을 한 번 잘 못 잡으니깐 다른 방법이 생각이 나질 않았다. ㅠㅠ

 

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)
 
#참고 https://br-brg.tistory.com/9

 

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