백준 15989 c++

경우의 수를 직접 구하며 규칙을 찾으려 했는데 찾지 못했다.
i는 1일 때 : 1
i는 2일 때 : 2
i는 3일 때 : 3
i는 4일 때 : 4
i는 5일 때 : 5
i는 6일 때 : 7
i는 7일 때 : 8
i는 8일 때 : 10
i는 9일 때 : 12
i는 10일 때 : 14
i는 11일 때 : 16
i는 12일 때 : 19

이런식으로는 규칙을 찾지 못했다.

1로 시작하는 경우, 2로 시작하는 경우, 3으로 시작하는 경우로 2차원 배열을 만들어 각각 구해보았다.

#include <iostream>
#include <vector>

using namespace std;

void make_DP(vector<vector<int>>& DP) {
	//cout << "make_DP\n";
	int i;

	DP.resize(10001, vector<int>(4, 0));
	DP[1][1] = 1;//1을 1로 시작하는 경우
	DP[2][1] = 1;//2을 1로 시작하는 경우
	DP[2][2] = 1;//2를 2로 시작하는 경우
	DP[3][1] = 1;//3을 1로 시작하는 경우
	DP[3][2] = 1;//3을 2로 시작하는 경우
	DP[3][3] = 1;//3을 3으로 시작하는 경우
	
	for (i = 4; i < DP.size(); i++) {
		DP[i][1] = 1;//i를 1로 시작하는 경우
		DP[i][2] = DP[i-2][1] + DP[i-2][2];//i를 2로 시작하는 경우
		DP[i][3] = DP[i - 3][1] + DP[i - 3][2] + DP[i-3][3];//i를 3으로 시작하는 경우
	}

	//for (i = 1; i < DP.size(); i++) {
	//	cout << DP[i][1] << "\t" << DP[i][2] << "\t" << DP[i][3] << "\n";
	//}

	return;
}

int find_answer(int n, vector<vector<int>>&DP) {

	cout << DP[n][1] << " + " << DP[n][2] << " + " << DP[n][3] << "\n";

	return DP[n][1] + DP[n][2] + DP[n][3];
}

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

	int T, i, n;
	vector<vector<int>> DP;

	make_DP(DP);
	
	cin >> T;
	for (i = 0; i < T; i++) {
		cin >> n;
		cout << find_answer(n, DP) << "\n";
	}

	return 0;
}