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

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

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

이전에 풀었던 1,2,3 더하기 문제는 순서와 숫자의 중복이 상관없는 순열과 같은 방식의 문제였다.

 

하지만 이번 문제는 순서는 상관없지만 숫자가 두번이상 나오는 경우는 제외하는 방식이다.

 

dp 방식으로 해결하였다.

 

경우의 수를 살펴보자면

 

dp[1] = 1                    총 1가지

dp[2] = 2                    총 1가지

dp[3] = 2 + 1

            1 + 2 

            3                    총 3가지

dp[4] = 1 + 2 + 1

            3 + 1

            1 + 3              총 3가지

dp[5] = 2 + 1 + 2

            3 + 2

            2 + 3

            1 + 3 + 1        총 4가지

dp[6] = 2 + 1 + 2 + 1

            3 + 2 + 1

            2 + 3 + 1

            1 + 2 + 1 + 2

            3 + 1 + 2

            1 + 3 + 2

            2 + 1 + 3

            1 + 2 + 3       총 8가지

dp[7] = 9가지

 

풀었던 방법은 이전과 비슷한데 dp[6]이라면 dp[5]에 경우의 수 중에서 가장 오른쪽이 1이 아닌 경우만 오른쪽에 +1을 붙여주고

 

dp[4]에서는 가장 오른쪽이 2가 아닌 경우만 오른쪽에 +2를 붙이고

 

dp[3]에서는 가장 오른쪽이 3이 아닌 경우만 오른쪽에 +3을 붙여서 경우를 만들었다.

 

따라서 dp[i] = dp[i-1] - (가장 오른쪽이 1이 아닌 경우) + dp[i-2] - (가장 오른쪽이 2가 아닌 경우) + dp[i-3] - (가장 오른쪽이 3이 아닌경우)

 

이렇게 나타낼 수 있다.

 

가장 오른쪽이 1이 아닌경우를 어떻게 찾을 수 있을까 고민하던 중 이전에 dp값 즉 dp[i-1]을 만들때는 dp[i-2]중에 오른쪽이 1이 아닌경우에1을 붙여서 만들었기 때문에 그것을 생각하며 식을 다시 써보았다.

 

dp[i] = dp[i-1] - (dp[i-2]에서 가장 오른쪽이 1이 아닌경우) + dp[i-2] - (dp[i-4]에서 가장 오른쪽이 2가 아닌경우) + dp[i-3] - (dp[i-6]에서 가장 오른쪽이 3이 아닌경우)

 

이렇게 가다보면 한도 끝도 없이 뒤로 돌아가게 된다. 풀 수가 없다.

 

따라서 배열 자체를 1로 끝나는 경우 2로 끝나는 경우 3으로 끝나는 경우를 2차원 배열로 만들어 풀기로 한다.

 

또한 이문제는 테스트 케이스마다 n까지의 dp를 다시 계산하는게 비효율적이여서 미리 100001까지 구해준 다음 풀어주었다.

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[100001][4] = { 0, };
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	dp[1][1] = dp[2][2] = 1;
	dp[3][1] = dp[3][2] = dp[3][3] = 1;
 
	for (int i = 4; i < 100001; i++)
	{
		dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % 1000000009;
		dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % 1000000009;
		dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % 1000000009;
	}
 
	int t;
	cin >> t;
 
	for (int test_case = 1;test_case <= t; test_case++) {
		int n;
		cin >> n;
 
		cout << ((long long)dp[n][1] + dp[n][2] + dp[n][3]) % 1000000009 << "\n";
	}
 
	return 0;
}

 

다 풀고도 마지막의 출력 때문에 애먹었다.

 

int 형으로 저장된 dp값을 세개를 합치므로 long long 형으로 받아줘야하고 마지막에도 1000000009를 나누어 줘야한다.