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

처음에 보자마다 dp라는 것도 몰랐고..^^

규칙 찾는것도 오래 걸렸다.  2부터 dp를 사용하려고 했던것이 문제였다. 1,2,3 을 구해놓고 해야했던것..

이렇게 저렇게 해봤는데 중복되는 조합이 생겨서 해맸다. 

결론은

n-1경우의 수 +1                        ex) n=4        3 +1 ,  1  2 +1  ,  2  1 + 1 , 1 1 1 +1      4개                         

n-2경우의 수 +2                                          1 1 +2  ,  2 + 2                                  2개

n-3경우의 수 +3                                          1 + 3                                                1개                                 

으로 구하면 된다.  

#include<iostream>

using namespace std;
int num[12];
// 처음에 문제 보고 어떻게 풀어야하지 고민하다가 알고리즘 분류를 봤는데 dp.. 생각을 못했다.

int main()
{
	int T;
	cin >> T;
	num[1] = 1;
	num[2] = 2;
	num[3] = 4;
	for (int i = 4; i < 11; i++)
	{
		for (int j = 1; j <=3 ; j++)
		{
			
			num[i] += num[i - j];
		}
		
	}
	while (T--) {
		int n;
		cin >> n;
		cout << num[n] << endl;
	}
	
}