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

www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

[풀이]

DP로 풀 수 있는 문제였다.

중복을 피하기 위해 오름차순으로만 더한다.

DP[i][1]: 정수 i를 만들 때 1로 끝나는 경우 -> 그 이전에 1만 올 수 있다.

DP[i][2]: 정수 i를 만들 때 2로 끝나는 경우 -> 그 이전에 1과 2가 올 수 있다.

DP[i][3]: 정수 i를 만들 때 3으로 끝나는 경우 -> 그 이전에 1과 2와 3이 올 수 있다.

 

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]

 

#include <iostream>
#define Max 10001
using namespace std;

int DP[Max][4] = { 0, };
int curN = 0;
int T;

void solution() {
	DP[0][1] = 1;
	DP[1][1] = 1;
	for (int i = 2; i <= 10000; i++) {
		DP[i][1] = DP[i - 1][1];
		DP[i][2] = DP[i - 2][1] + DP[i - 2][2];
		if (i >= 3)
			DP[i][3] = DP[i - 3][1] + DP[i - 3][2] + DP[i - 3][3];
	}
}

int main() {
	int n;
	cin >> T;
	solution();
	curN = 3;
	while (T--) {
		cin >> n;
		cout << DP[n][1] + DP[n][2] + DP[n][3] << '\n';
	}
	return 0;
}