[백준/C++] 9095 1, 2, 3 더하기 (S3)

유형	난이도	완료일	링크	특이사항
DP	실버3	23/03/26	https://www.acmicpc.net/problem/9095

 

 

내 풀이

#include <iostream>
#include <algorithm>

using namespace std;

int main(void)
{
	int t;
	cin >> t;
	
	int n;
	
	int arr[11] = {};
	
	arr[0] = 1;
	arr[1] = 2;
	arr[2] = 4;
	arr[3] = 7;
	
	for(int i= 4; i<11; i++)
	{
		arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
	}
	
	for(int i = 0; i<t; i++)
	{
		cin >> n;
		
		cout << arr[n-1]<<"\\n";
	}
	
}

  1일 때의 답, 2일 때의 답, 3일때의 답, … 6일때의 답까지 나열해보자 점화식을 얻을 수 있었다.

이렇게 무작정 나열해보지 않았다면 점화식을 찾을 수 없었을 것이다. 규칙을 깨닫지 못하고 나열해서 알아내는 방식의 문제가 싫다.

1,2,3의 조합만 생각하면 되고 수가 11까지밖에 없으므로 이렇게 규칙을 찾지 말고 모든 경우를 탐색하는 방법도 가능할 것이다.