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

경우의 수가 많다. dp문제로 보이므로 규칙을 찾을때까지 적어본다.

각 숫자를 1,2,3의 합으로 구하는 방법을 쭉 적어보다가 규칙을 발견할 수 있었다.

4부터 보게되면

네모를 친 1+1+1+1, 2+1+1, 1+2+1, 3+1은 4보다 1 작은 3의 네가지 경우의 수의 뒤에 1을 더한 형태

세모를 친 2+2, 1+1+2의 경우에는 4보다 2 작은 2의 2가지 경우의 수의 뒤에 2를 더한 형태

역삼각형의 경우는 4보다 3 작은 1의 1가지 경우의 수의 뒤에 3을 더한 형태다.

 

dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

피보나치수가 생각나는 형태의 점화식을 찾을 수 있었다.

#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
long long dp[12];
long long arr[12];
int countnum;
int main()
{
	cin >> countnum;
	dp[0] = 1;
	dp[1] = 2;
	dp[2] = 4;
	for (int i = 3; i < 12; i++)
	{
		dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
	} 
	for (int i = 0; i < countnum; i++)
	{
		int temp;
		cin >> temp; 
		cout << dp[temp - 1] << endl;
	}
}