백준 / 다이나믹 프로그래밍 / 15990번 / 1, 2, 3 더하기 5 / C++

문제

정수 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 

3

4 7 10

예제 출력 1 

3 9 27

 

#include <iostream>
using namespace std;

const int N = 1e5 + 1;
const int divisor = 1e9 + 9;

int dp[N][4];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;
		
	int t;
	cin >> t;
	
	for(int i=4; i<N; i++) {
		dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % divisor;
		dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % divisor;
		dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % divisor;
	}
	
	while(t--) {
		long long result = 0;
		int n;
		cin >> n;
		
		for(int i=1; i<=3; i++) {
			result += dp[n][i];
		}
		
		cout << result % divisor << '\n';
	}
		
	return 0;
}

---

앞의 1, 2, 3 더하기 문제를 풀었다면 알고리즘을 활용해서 풀 수 있다.

그 전 문제와 다른점은 1차원 배열이 아닌 2차원 배열이라는 점이다.

이 배열을 설명하자면, 예를들어 dp[3][1]은 1,2,3으로 3을 표현하는 방법중에 1로 끝나는것의 갯수이다.

다른 한 예시를 더 들자면, dp[4][2]는 1,2,3으로 4를 표현하는 방법중에 2로 끝나는것의 갯수이다.

 

위의 방법으로 아래와 같은 알고리즘을 얻을 수 있다.

우리가 입력한 값이 n이라 하면, dp[n][1] + dp[n][2] + dp[n][3]을 구하면 된다.

다시 말해 1,2,3으로 n을 표현하는데 끝에 1이올경우, 2가올경우, 3이올경우를 모두 더해주면 된다.

 

그런데 dp[n][1]은 어떻게구할까?

이 문제에서는 같은 수가 연속으로 올 수 없으므로 마지막에 1을 더하는 방법은 그 전에 1이 또 올수가 없다.

즉 n = ... + 2 or 3 + 1이 된다는 말이다.

여기서 양변에 -1을 해주면 n-1 = ... + 2 or 3 이 된다.

따라서 우리는 dp[n][1] = dp[n-1][2] + dp[n-1][3]이 되는것을 알 수가 있다.

 

dp[n][2]도 위와 같은 방법으로 구할 수 있다.

n = ... + 1 or 3 + 2가 되니

n-2 = ... + 1 or 3이 된다.

따라서 dp[n][2] = dp[n-2][1] + dp[n-2][3]이 된다.

 

dp[n][3]도 마찬가지이다.

dp[n][3] = dp[n-3][1] + dp[n-3][2]이다.

 

dp[1][1]부터 dp[3][3]까지는 모두 방법이 한가지씩 밖에 없기때문에 미리 초기화를 시켜주면된다.

 

그리고 주의할것은 위의 코드에서 result를 long long으로 선언한 것인데 이 이유는 아래와 같다.

우리는 결과를 얻기 위해 dp[n][1] + dp[n][2] + dp[n][3]을 해주어야 한다.

이때 더하는 수 각각은 int범위 안에 있을 수 있으나, 모두 더하면 int의 범위를 넘을 수 있다.

따라서 result는 long long형으로 선언해주는 것이다.

 

코드를 보면서 위의 설명을 보면 쉽게 이해할 수 있을것이다.