[백준] 9095번 1, 2, 3 더하기

 

해당 문제는 다이나믹 프로그래밍을 사용하여 해결하는 문제이다.

 

 

각 정수들의 관계는 아래와 같이 정의할 수 있다.

 

정수 N에 대한 방법의 수를 N이라 할 때,

N = (N-1) + (N-2) + (N-3)

 

실행코드는 아래와 같다.

#include <iostream>
using namespace std;

int DP[10] = { 0, 1, 2, 4 };		// 각각 0, 1, 2, 3에 대한 답

int main()
{
	int T;
	cin >> T;
	for (int i = 4; i < 12; i++)	// 4번부터 채워 넣기 시작
		DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3];
	for (int i = 0; i < T; i++)
	{
		int num;
		cin >> num;
		cout << DP[num] << endl;
	}

	return 0;
}