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

문제 

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

9095번: 1, 2, 3 더하기

먼저 규칙을 찾았다. 

 

규칙

n	방법	방법의 수
1	1	1
2	1+1 , 2	2
3	1+1+1, 1+2, 2+1, 3	4
4	1+1+1+1, 1+1+2, 1+2+1,2+1+1, 2+2, 1+3, 3+1	7
5	1+1+1+1+1, 1+1+1+2,1+1+2+1,1+2+1+1+,2+1+1+1,2+2+1,2+1+2,1+2+2, 2+3+3+2, 3+1+1,1+3+1,1+1+3	13
6	1+1+1+3, 1+1+3+1, 1+3+1+1, 3+1+1+1, 1+1+2+2, 1+2+2+1, 1+2+1+2, 2+2+1+1, 2+1+2+1, 2+1+1+2, 1+3+2, 1+2+3,2+1+3,2+3+1,3+1+2,3+2+1, 3+3, 2+2+2	24

 

n	방법의 수
1	1
2	2
3	4
4	7 (1+2+4)
5	13 (2+4+7)
6	24 (4+7+13)

따라서 

N(n) : n을 1,2,3의 합으로 나탄래 수 있는 방법의 수 

N(n) = N(n-1) + N(n-2) + N(n-3)이다. 

 

코드 

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

int main()
{
	//입출력 속도
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector <int> v(12,0);
	vector <int> testCase;
	v[1] = 1;
	v[2] = 2;
	v[3] = 4;

	int t;
	int n;
	
	for (int i = 4; i < 12; i++)
	{
		v[i]=(v[i - 1] + v[i - 2] + v[i - 3]);
	}
	
	cin >> t;

	for (int j=0; j<t; j++)
	{
		cin >> n;
		cout << v[n] << '\n';
	}
	

	return 0;
}