(c++)백준 9095번: 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

※점화식※

dp[x] : x를 1,2,3의 합으로 나타내는 방법의 수

dp[1] = 1 (1)

dp[2] = 2 (2, 1+1)

dp[3] = 4 (1+1+1, 1+2, 2+1, 3)

 

x번째 값은 x-3번째 값에 +3을 하거나, x-2번째 값에 +2를 하거나, x-1번째 값에 +1을 하므로,

dp[x] = dp[x-3] + dp[x-2] + dp[x-1]이 된다.

#include <iostream>
using namespace std;

int T, n;
int dp[11];
int cnt = 4;

void DP() {
	for (int i = cnt; i <= n; i++) {
		dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
	}
	cnt = n + 1;
	cout << dp[n] << endl;
}

int main() {
	cin >> T;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	while (T--) {
		cin >> n;
		//이전 테스트케이스에서 이미 구한 값이면 바로 출력
		if (n < cnt) {
			cout << dp[n] << endl;
			continue;
		}
		DP();
	}
	return 0;
}