[DP] 15990 1, 2, 3 더하기 5 - 오답노트

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

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

- 문제 파악

정수 N과 N개의 정수가 주어진다. 각각의 정수를 1,2,3의 합으로 나타낼 수 있는 경우의 수를 출력하라. 단, 1,2,3 중 1개 이상의 숫자를 써야하고 연속해서 사용할 수 없다.

 

- 나의 접근

시간복잡도를 신경안쓰고 일단

초항으로 1, 2, 3을 먼저 초기화하고 4부터 for문을 돌리도록 했는데

초항에 대한 문자열을 초기화하여 무식하게 앞뒤로 붙혀가면서 연속되면 경우의 수에서 제외 해버리는 알고리즘으로 접근했으나, 예상대로 시간초과로 막혔다. (굳이 제출도 안함.)

 

- 정답

예상대로 점화식으로 푸는 문제였으나 나는 1차원 배열에 어떻게든 점화식을 구하려고 했지만, 다차원 배열로 접근하면 의외로 쉽게 점화식을 얻을 수 있다.

 

D[i][n] 은 i를 만드는 수의 조합중 n이 마지막에 있는 경우이다.

점화식 : 
D[i][1] = (D[i - 1][2] + D[i - 1][3]) 
D[i][2] = (D[i - 2][1] + D[i - 2][3]) 
D[i][3] = (D[i - 3][2] + D[i - 3][1]) 

D[i][1]는 i를 만드는 수의 조합중 1이 가장 마지막에 있을때이다.

i - 1 에서 1을 더 하면 i가 되고, 1을 연속으로 사용하면 안되므로 D[i - 1][2]와 D[i - 1][3] 를 더한다.

 

D[i][2]는 i를 만드는 수의 조합중 2가 가장 마지막에 있을때이다.

i - 2 에서 2을 더 하면 i가 되고, 2을 연속으로 사용하면 안되므로 D[i - 1][1]와 D[i - 1][3] 를 더한다.

 

D[i][3]는 i를 만드는 수의 조합중 3이 가장 마지막에 있을때이다.

i - 3 에서 3을 더 하면 i가 되고, 3을 연속으로 사용하면 안되므로 D[i - 1][2]와 D[i - 1][1] 를 더한다.

 

#include "bits/stdc++.h"

using namespace std;

int n;
unsigned long long D[100002][4];

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(0);

	D[1][1] = 1;
	D[2][2] = 1;

	D[3][1] = D[1][1] + D[2][1];	// 21
	D[3][2] = D[1][2] + D[2][2];	// 12
	D[3][3] = 1;					// 3


	for (int i = 4; i <= 100000; i++)
	{

		D[i][1] = (D[i - 1][2] + D[i - 1][3]) % 1000000009; // 4 1 = 1 + 1 = 2
		D[i][2] = (D[i - 2][1] + D[i - 2][3]) % 1000000009; // 4 2 = 0 + 0
		D[i][3] = (D[i - 3][2] + D[i - 3][1]) % 1000000009; // 4 3 = 0 + 1 = 1

	}

	cin >> n;
	while (n--)
	{
		int k;
		cin >> k;

		cout << (D[k][1] + D[k][2] + D[k][3]) % 1000000009 << "\n";


	}

}