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

문제

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

풀이

2차원 배열 점화식

4를 1, 2, 3의 합으로 나타내면
① 3 + 1
② 2 + 2
③ 1 + 3

1) 4를 만들 수 있는 수식 중에서, 1로 끝나는 수식은 3을 만드는 수식에서 1을 더하는 것
즉, dp[4][1] = dp[3][1]
=> dp[n][1] = dp[n-1][1]

2) 4를 만들 수 있는 수식 중에서, 2로 끝나는 수식은 2를 만드는 수식에서 1로 끝나는 것과 2로 끝나는 것에 2를 더하는 것
즉, dp[4][2] = dp[2][1] + dp[2][2]
=> dp[n][2] = dp[n-2][1] + dp[n-2][2]

3) 4를 만들 수 있는 수식 중에서, 3으로 끝나는 수식은 1을 만드는 수식에서 1, 2, 3으로 끝나는 것에 3을 더하는 것
즉, dp[4][3] = dp[1][1] + dp[1][2] + dp[1][3]
=> dp[n][3] = dp[n-3][1] + dp[n-3][2] + dp[n-3][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] (n >= 4)

코드

#include <iostream>

using namespace std;

long long dp[10001][4];

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

	dp[1][1] = 1;
	dp[2][1] = 1;	dp[2][2] = 1;
	dp[3][1] = 1;	dp[3][2] = 1;	dp[3][3] = 1;
	for (int i = 4; i <= 10000; i++) {
		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];
	}

	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		cout << dp[n][1] + dp[n][2] + dp[n][3] << '\n';
	}

	return 0;
}