[백준 실버3] 9095 1, 2, 3 더하기

 

 

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

 

피보나치 수열 처럼 n-1 n-2 n-3을 더해주면 된다.

직접 손으로 그려가며 경우의 수를 써봤는데

 

1일 땐 1의 경우의 수

2일 땐 2의 경우의 수

3일 땐 4의 경우의 수

4일 땐 1 + 2 + 4 = 7의 경우의 수였으며,

5일 땐 7 + 4 + 2 = 13의 경우의 수를 가졌다.

 

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;




int main(void) {

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

	int T;

	cin >> T;

	while (T-- != 0)
	{
		int n = 0;
		cin >> n;


		if (n == 0) {
			cout << "0" << endl;
			continue;
		}
		else if (n == 1) {
			cout << "1" << endl;
			continue;
		}
		else if (n == 2) {
			cout << "2" << endl;
			continue;
		}
		else if (n == 3) {
			cout << "4" << endl;
			continue;
		}

		vector<int> arr;
		arr.push_back(0);
		arr.push_back(1);
		arr.push_back(2);
		arr.push_back(4);
		for (int i = 3; i < n; i++) {
			arr.push_back(arr[i - 2] + arr[i - 1] + arr[i]);
		}

		cout << arr.back() << endl;
	}

	return 0;
}