[BOJ] 15990 1,2,3 더하기 5(다이나믹 프로그래밍)

1. 문제

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

2. 아이디어

• 5를 예시로 들자면
  
  5의 1시작 = 4의 2시작 + 5의 3시작
  5의 2시작 = 3의 1시작 + 3의 3시작
  5의 3시작 = 2의 1시작 + 2의 2시작

3. 풀이과정

1) ❌WRONG❌

• 코드

#include <iostream>
using namespace std;

#define mod 1000000009

int num1[1000000 + 1];
int num2[1000000 + 1];
int num3[1000000 + 1];

int main() {
	int T; // Testcase 수
	int n;

	cin >> T;

	num1[1] = num2[2] = num3[3] = 1;
	num1[3] = num2[3] = 1;

	while (T--)
	{
		cin >> n;

		for (int i = 4; i <= n; ++i)
		{
			num1[i] = (num2[i - 1] + num3[i - 1]) % mod;
			num2[i] = (num1[i - 2] + num3[i - 2]) % mod;
			num3[i] = (num1[i - 3] + num2[i - 3]) % mod;
		}

		cout << (num1[n] + num2[n] + num3[n]) % mod << '\n';

		for (int i = 4; i <= n; ++i)
		{
			num1[i] = 0;
			num2[i] = 0;
			num3[i] = 0;
		}
	}
	return 0;
}
}

• 틀린 이유
  int 범위를 넘는 답도 존재한다.
  따라서 num배열의 자료형이 int인 것은 적절하지 않다.

2) ⭕RIGHT⭕

• 코드

#include <iostream>
using namespace std;

#define mod 1000000009

long long num1[1000000 + 1];
long long num2[1000000 + 1];
long long num3[1000000 + 1];

int main() {
	int T; // Testcase 수
	int n;

	cin >> T;

	num1[1] = num2[2] = num3[3] = 1;
	num1[3] = num2[3] = 1;

	while (T--)
	{
		cin >> n;

		for (int i = 4; i <= n; ++i)
		{
			num1[i] = (num2[i - 1] + num3[i - 1]) % mod;
			num2[i] = (num1[i - 2] + num3[i - 2]) % mod;
			num3[i] = (num1[i - 3] + num2[i - 3]) % mod;
		}

		cout << (num1[n] + num2[n] + num3[n]) % mod << '\n';
		
    		 /* 초기화 */
		for (int i = 4; i <= n; ++i)
		{
			num1[i] = 0;
			num2[i] = 0;
			num3[i] = 0;
		}
	}
	return 0;
}