[C++] BaekJoon 9095 1, 2, 3 더하기

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

---

정수 n이 주어졌을 때 1, 2, 3의 숫자만을 이용해서 합을 나타내고 그 경우의 수를 구하는 문제이다. 

 

코드

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

int main()
{
	int T;
	int N;
	cin >> T;
	vector <int> arr(12);
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;
	for (int i = 4; i < 12; i++)
	{
		arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
	}
	for (int i = 1; i <= T; i++)
	{
		cin >> N;
		cout << arr[N] << "\n";
	}
		
}

 

설명

예를 들어 설명하겠다. 

 

< N = 1>

1

경우의 수 : 1

 

< N = 2>

1 + 1

2

경우의 수 : 2

 

< N = 3 >

1 + 1 + 1

1 + 2

2 + 1

3

경우의 수 : 4

 

< N = 4 >

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

2 + 1 + 1

1 + 3

3 + 1 

2 + 2

경우의 수 : 7

 

< N = 5 >

1 + 1 + 1 + 1 + 1

1 + 1 + 1 + 2 

1 + 1 + 2 + 1

1 + 2 + 1 + 1

2 + 1 + 1 + 1

1 + 1 + 3

1 + 3 + 1

3 + 1 + 1

2 + 2 + 1

2 + 1 + 2

1 + 2 + 2

2 + 3

3 + 2

 

경우의 수 : 13

....

 

살펴보면 < N = 4 > 의 경우의 수 = < N = 3 > + < N = 2 > + < N = 1 > 의 경우의 수

이 규칙을 이용해서 코드를 구현하였다.