백준 9095 1, 2, 3 더하기

간단한 문제입니다. 

동적 프로그래밍의 개념을 알고 있다면 쉽게 해결할 수 있습니다.

기존의 동전문제와 다른 점은 1+3과 3+1 같이 순서를 구분한다는 점입니다. 

주어진 예시 입력값 4의 경우를 말씀드리겠습니다. 

이 문제는 1과 2와 3만을 이용해 합을 나타내는데 주목해주세요.

4는 다음의 합의 경우로 나타낼 수 있습니다. 

1+~~

2+~~

3+~~

의 3가지가 존재합니다. 

4의 경우 1+3을 만드는 가지수, 2+2를 만드는 가지수, 3+3을 만드는 가지수를 모두 더해 주면 된다는 의미입니다. 

점화식으로 나타내면 다음과 같습니다. 

f(n)=f(n-1)+f(n-2)+f(n-3)

동적 프로그래밍을 하기 위해서는 초기값이 필요합니다. 이 문제에서 사용할 초기값은 1을 만드는 가지수, 2를 만드는 가지수, 3을 만드는 가지수입니다. 

먼저 1, 2, 3을 가지고 1을 만드는 경우는 1가지 밖에 존재하지 않습니다. 즉, dp[1]=1이 됩니다.ㅏ 

2를 만드는 경우는 1+1과 2로 2가지의 경우가 존재합니다. dp[2]=2가 됩니다. 

3을 만드는 경우는 1+1+1, 1+2, 2+1, 3으로 4가지가 존재합니다.  dp[3]=4가 됩니다. 

이 초기값들을 이용해 코딩하면 문제를 해결할 수 있습니다.

아래는 제가 제출한 코드입니다.

#include <iostream>

using namespace std;

int main()
{
	int n;
	int T;
	int dp[11] = { 0 };

	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	for (int j = 4;j <= 10;j++) {
		dp[j] = dp[j - 1] + dp[j - 2] + dp[j - 3];
	}

	cin >> T;

	for (int i = 0;i < T;i++) {
		cin >> n;
		cout << dp[n] << endl;
	}

	return 0;
}