<Baekjoon> #15989 Dynamic Programming_1,2,3 더하기 4 c++

#15989 1,2,3 더하기 4

문제는 1,2,3 을 이용하여 정수 n을 만드는 방법을 나타내는 개수를 구하는 것이다.
주의할 점은 4를 만들 때, 2+1+1, 1+2+1, 1+1+2 는 모두 같은 것으로 취급한다. 여기서 한가지 생각해야 할 점은 이 순서를 오름차순이나 내림차순으만 나타낸다.

여기에서는 오름차순으로 나타내본다.

dp[i][0] 은 정수 i를 만들기 위해 나타내는 방법중 마지막이 1로 끝나는 것
dp[i][1] 은 정수 i를 만들기 위해 나타내는 방법중 마지막이 2로 끝나는 것
dp[i][2] 은 정수 i를 만들기 위해 나타내는 방법중 마지막이 3로 끝나는 것

(*헷갈리지 않게 long long dp[MAX][4] 로 선언해서 dp[i][1], dp[i][2], dp[i][3] 으로 해도 괜찮을 거 같다)

dp[1][0]=1
dp[2][0]= {1+1}, dp[2][1]= {2}
dp[3][0]= {1+1+1}, dp[3][1]= {1+2}, dp[3][2]= {3}

dp[4][j] 부터는 일반화를 해보자
dp[4][0]= {1+1+1+1} : dp[3][] 에서 1을 더한 것
dp[4][1]= {1+1+2}, {2+2} : dp[2][] 에서 1을 더한 것
dp[4][2]= {1+3} :dp[1][] 에서 3을 더한 것

따라서 이렇게 나타낼 수 있다.
dp[i][0] = dp[i-1][0]
dp[i][1] = dp[i-2][1]
dp[i][2] = dp[i-3][2]

전체 코드

#include<iostream>
#include <vector>
const int MAX = 10001;
using namespace std;
long long dp[MAX][3];

void findDP() {
	dp[1][0] = 1;
	dp[2][0] = 1; dp[2][1] = 1;
	dp[3][0] = 1; dp[3][1] = 1; dp[3][2] = 1;

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