[Silver 3] 9095번 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

이 문제는 DP를 통해 해결할 수 있다.

 

문제의 조건은 아래와 같이 변한다.

1	2	3	4	5	6	7
1	2	4	7	13	24	44

 

위 표를 통해 점화식을 세워보면

if N > 3

dp[N] = dp[N-1] + dp[N-2] + dp[N-3]이 성립한다.

 

#include <iostream>
using namespace std;

int N;
int dp[11];

int main() {
	int T;
	cin >> T;

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;
	for (int j = 4; j < 11; j++) {
		dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
	}
	for (int i = 0; i < T; i++) {
		cin >> N;
		cout << dp[N] << '\n';
	}
}