백준 9095번 1,2,3 더하기 (C++)

백준 9095번

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

9095번: 1, 2, 3 더하기

 

 

 

 

문제

 

 

문제 설명

입력받은 정수들을 1,2,3으로 조합해서 몇가지가 있는지 출력

 

 

접근

DP로 접근

 

1 => 1가지

2 => 2가지

3 => 4가지 디폴트값

 

 

 

코드

#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>

using namespace std;

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

	int N;
	cin >> N;
	int T;
	int arr[11];
	arr[1] = 1;
	arr[2] = 2;
	arr[3] = 4;


	for (int i = 0; i < N; i++) {
		cin >> T;
		for (int j = 4; j <= T; j++)
		{
			arr[j] = arr[j - 1] + arr[j - 2] + arr[j - 3];
		}
		cout << arr[T]<<endl;
	}
	
	return 0;
}

 

 

문제풀이

규칙을 찾으면서 1씩 증가시킴

 

1 => 1

2 => 2

3 => 4

4 => 7

5 => 13

6 => 24

N => N-1 + N-2 + N-3