[C/C++] 백준 - 15990번 : 1, 2, 3 더하기 5

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

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

문제

정수 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로 나눈 나머지를 출력한다.

 

입력한 수를 1,2,3의 합으로 나타내는데 같은 수를 두 번 연속으로 사용하지 않는 방법의 총 경우의 수를 구하는 문제이다. 일단 선제 조건이 어떻게 되냐면, 1, 2, 3 모두 각 수를 덧셈 조합없이 1, 2, 3 자체로 각 수를 나타낼 수 있다.

그리고 각 수가 연속해서 나오면 안되기 때문에 1 다음에는 똑같은 1이 올 수 없고, 2 다음에는 똑같이 2가 올 수 없으며, 3 다음에는 똑같이 3이 올 수 없다. 너무 당연한 말이지만 이걸로 점화식을 만드는 것이다.

 

DP[i][j]  -> i를 만드는 조합의 마지막 수가 j

ex) DP[3][2] 는 x + 2 = 3이 되는 식

 

이렇게 되면, 위에서 말한 선제조건에 따라

DP[1][1] = 1

DP[2][2] = 2

DP[3][3] = 3

이 되며, 

DP[i][1] = DP[?][2] + DP[?][3]

DP[i][2] = DP[?][1] + DP[?][3]

DP[i][3] = DP[?][1] + DP[?][2]

가 된다.  그럼 이제 ?만 알아내면 되는데, 이건 너무도 당연하게

DP[i][1] 은 i를 만들 때 마지막 수가 1이라는 식이므로, i는 i-1이 되는것이다

그래야 DP[i][1] = (i-1) + 1 = i 가 되기 때문이다

나머지 식도 마찬가지로 이런 형태로 정의하고 문제의 범위인 100000까지 for문을 통해 구하면

O(N)에 시간복잡도로 답을 구할 수 있다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#define Mod 1000000009
using namespace std;

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

long long DP[100002][4];

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

	DP[1][1] = 1;
	DP[2][2] = 1;
	DP[3][3] = 1;
	for (int i = 2; i <= 100000; i++) {
		for (int j = 1; j <= 3; j++) {
			if (i > j) {
				if (j == 1) DP[i][j] = (DP[i - 1][2] + DP[i - 1][3]) % Mod;
				if (j == 2) DP[i][j] = (DP[i - 2][1] + DP[i - 2][3]) % Mod;
				if (j == 3) DP[i][j] = (DP[i - 3][1] + DP[i - 3][2]) % Mod;
			}
		}
	}

	int T; cin >> T;
	for (int testCase = 0; testCase < T; testCase++) {
		int x; cin >> x;
		cout << (DP[x][1] + DP[x][2] + DP[x][3]) % Mod << endl;
	}
	
	return 0;
}