[코테] 백준 다이나믹 프로그래밍 15990번 문제

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

문제 링크

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

문제 설명

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

• 1+2+1
• 1+3
• 3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

문제풀이

점화식을 이용하는 기법으로 연속된 숫자가 오면 안되므로 n을 1,2,3의 합으로 나타내는 방법은 아래의 수들의 합으로 나타낸다. 기존의 1차원 배열에서 마지막 숫자가 1,2,3인지에 따라 저장하는 2차원 배열로 저장하게 된다.

1. dp[i][1] = dp[i-1][2] + dp[i-1][3]
2. dp[i][2] = dp[i-2][1] + dp[i-2][3]
3. dp[i][3] = dp[i-3][1] + dp[i-3][2]

import sys
input = sys.stdin.readline

N = int(input())
DIV_NUM = 1000000009
MAX_NUM = 100001
dp = [[0 for _ in range(4)] for _ in range(MAX_NUM)]    

dp[1][1] = 1
dp[2][1] = 0
dp[2][2] = 1
dp[3][1] = 1
dp[3][2] = 1
dp[3][3] = 1

for i in range(4, MAX_NUM) :
    dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % DIV_NUM
    dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % DIV_NUM
    dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % DIV_NUM

for _ in range(N) :
    num = int(input())
    print(sum(dp[num]) % DIV_NUM)