BOJ-15989 1,2,3 더하기 4

필요한 지식

1. 동적계획법

접근

• n이 10,000 까지.

• 순서만 다른것은 같은 것으로 친다.

• 점화식

dp[i][0] = dp[i - 1][0]
dp[i][1] = dp[i - 2][0] + dp[i - 2][1]
dp[i][2] = dp[i - 3][0] + dp[i - 3][1] + dp[i - 3][2]

• dp[i][j] : i의 합이 j+1로 끝나는 경우의 수

• dp[i][0] : i가 1로 끝나는 경우이므로 i-1이 1로 끝났던 경우(dp[i-1][0])의 값을 가진다.

• dp[i][1] : i가 2로 끝나는 경우이므로 i-2가 1과 2로 끝났던 경우(dp[i-2][0],dp[i-2][1])를 더한 값을 가진다.

• dp[i][2] : i가 3으로 끝나는 경우이므로 i-3이 1,2,3으로 끝났던 경우(dp[i-3][0],dp[i-3][1],dp[i-3][2])를 더한 값을 가진다.

코드(C++)

#include <iostream>
using namespace std;
typedef long long ll;
ll dp[10001][3];
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	dp[1][0] = dp[2][0] = dp[2][1] = dp[3][0] = dp[3][1] = dp[3][2] = 1;
	for (int i = 4; i <= 10000; i++) {
		dp[i][0] = dp[i - 1][0];
		dp[i][1] = dp[i - 2][0] + dp[i - 2][1];
		dp[i][2] = dp[i - 3][0] + dp[i - 3][1] + dp[i - 3][2];
	}
	while (t--) {
		ll n; cin >> n;
		cout << dp[n][0] + dp[n][1] + dp[n][2] << "\n";
	}
	return 0;
}