[ DP - 9095 ] 1, 2, 3 더하기

 

---

접근법

 

직접 해 보는 것이 DP문제에서 규칙을 찾는 가장 쉬운 방법인 것 같다.

 

• 1 표현
  • 1
• 2 표현
  • 1+1
  • 2
• 3 표현
  • 1+1+1
  • 1+2
  • 2+1
  • 3

1,2,3은 각각 1,2,4가지로 표현 가능하다.

 

4를 1,2,3의 합으로 나타내보자.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 1+3
• 2+2
• 2+1+1
• 3+1

총 7가지인데, 처음이 1일 때 나머지 3을 나타낼 수 있는 가지수는 위에서 구한 4가지, 처음이 2일 때 나머지 2를 나타낼 수 있는 가지수는 2가지 그리고 처음이 1이면 1가지 이다.

 

따라서 DP[4] = DP[4-1] + DP[4-2] + DP[4-3] 으로 표현 가능하다. 이제 구현해보자.

---

정답

#include<iostream>
#include<vector>
using namespace std;

int32_t DP[12];

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

	int32_t s32_I, s32_T, s32_J;

	cin >> s32_T;

	vector<int32_t> st_Reuslt;
	for (s32_I = 0; s32_I < s32_T; s32_I++)
	{
		cin >> s32_J;
		st_Reuslt.push_back(s32_J);
	}

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

	for (s32_I = 4; s32_I <= 11; s32_I++)
	{
		DP[s32_I] = DP[s32_I - 1] + DP[s32_I - 2] + DP[s32_I - 3];
	}

	for (s32_I = 0; s32_I < s32_T; s32_I++)
	{
		cout << DP[st_Reuslt[s32_I]] << endl;
	}

	return 0;
}