백준 15989번 1, 2, 3 더하기 4 C++

출처 : https://www.acmicpc.net/problem/15989

 

간단한 dp문제일 줄 알았는데, 중복을 허용하지 않는다는 조건이 있어서 풀이를 생각하는데 시간이 조금 걸렸다.

생각해낸 해결법은 오름차순으로 정렬된 경우만 고려하는 것이다.

2차원 dp테이블을 만들어서 dp[i][j]는 i를 만드는 데 마지막에 사용한 숫자는 j 이라는 정보를 저장해서 문제를 해결하였다.

 

dp[4][1]은 4를 만드는데 마지막에 1이 사용되고, 오름차순으로 정렬된 경우만 고려하므로 3을 만들 때 마지막에 1이 사용된 경우만 가능하다. 그러므로 dp[4][1]=dp[3][1] 이기 때문에

dp[i][1]=dp[i-1][1] 이라는 점화식을 하나 얻을 수 있다.

 

dp[4][2]는 4를 만드는데 마지막에 2가 사용되고, 오름차순으로 정렬된 경우만 고려하기 때문에 2를 만들 때 마지막에 1이 사용된 경우와 2가 사용된 경우 두가지가 가능하다. 그러므로 dp[4][2]=dp[2][1]+dp[2][2] 이기 때문에

dp[i][2]=dp[i-2][1]+dp[i-2][2] 라는 점화식을 얻을 수 있다.

 

마지막으로 dp[4][3]은 4를 만드는데 마지막에 3이 사용되고, 오름차순으로 정렬된 경우만 고려하기 때문에 1을 만들 때 마지막에 1, 2, 3 이 사용된 경우 모두 가능하다. 그러므로 dp[4][3]=dp[1][1]+dp[1][2]+dp[1][1] 이기 때문에

dp[i][3]=dp[i-3][1]+dp[i-3][2]+dp[i-3][3] 이라는 점화식을 얻을 수 있다.

 

여기서 얻은 3개의 점화식을 이용해서 dp테이블을 채워가면서 dp[n][1]+dp[n][2]+dp[n][3]을 구하면 답을 얻을 수 있다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	int t, n;
	cin >> t;
	int dp[10001][4] = { 0 };
	dp[1][1] = 1;
	dp[2][1] = 1;
	dp[2][2] = 1;
	dp[3][1] = 1;
	dp[3][2] = 1;
	dp[3][3] = 1;
	for (int i = 4; i <= 10000; i++) {
		dp[i][1] = dp[i - 1][1];
		dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
		dp[i][3] = dp[i - 3][1] + dp[i - 3][2] + dp[i - 3][3];
	}
	while (t--) {
		cin >> n;
		int ans = dp[n][1] + dp[n][2] + dp[n][3];
		cout << ans << "\n";
	}
};