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

 

<코드>

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

int T, n, dp[12];

int main()
{
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	cin >> T;

	while (T--)
	{
		cin >> n;
		for (int i = 4; i <= n; i++)
		{
			dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
		}
		cout << dp[n] << '\n';
	}
	
}

 

풀이 방법

 

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

5를 만드는 방법 = 1과 4를 만드는 방법 + 2와 3을 만드는 방법+ 3과 2를 만드는 방법

1+1+1+1+1
1+1+1+2
1+1+2+1
1+1+3
1+2+1+1
1+2+2
1+3+1

2+1+1+1
2+1+2
2+2+1
2+3

3+1+1
3+2

 

 

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기