[BOJ/C++] 9095 1, 2, 3 더하기 : DP

문제

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

풀이

dp[0] = 0, dp[1] = 1, dp[2] = 2, dp[3] = 4

dp[4] = 3+1 => 3 만드는 경우의 수 +1 => 4
    = 2+2 => 2 만드는 경우의 수 +2 => 2
    = 1+3 => 1 만드는 경우의 수 +3 => 1
    = 7

dp[5] = 4+1 => 4 만드는 경우의 수 + 1 => 7
    = 3+2 => 3 만드는 경우의 수 + 2 => 4
    = 2+3 => 2 만드는 경우의 수 + 3 => 2
    = 1+4 => 1 만드는 경우의 수 + 4 // 1, 2, 3만을 이용해서 표현해야하므로 +4는 안됨
    = 13

최종적으로 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이라는 점화식을 도출할 수 있다.

4+1 3+2 이런 식으로 분해하는 건 알았는데 4+1과 1+4에서 겹치는 경우를 제외해야 하나? 생각함
근데 알고보니 1, 2, 3 더하기라서 +4인 경우는 불가능 한 거였다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int T;

	cin >> T;
	while (T--) {
		int N;
		vector<int> v;

		cin >> N;
		v.push_back(0); //0을 나타내는 경우의 수
		v.push_back(1); //1을 나타내는 경우의 수
		v.push_back(2); //2를 나타내는 경우의 수
		v.push_back(4); //3을 나타내는 경우의 수

		for (int i = 4; i <= N; i++) {
			int tmp;

			tmp = v[i - 1] + v[i - 2] + v[i - 3];
			v.push_back(tmp);
		}

		cout << v[N] << endl;
	}


	return 0;
}