9095번 1,2,3 더하기

최근 풀이 241105

: 재귀돌림.

• 문제를 보면 1,2,3의 원소값을 누적시키면서 재귀를 하면된다고 생각함.

• 기저 사례를 어떻게 처리할것인가?? 가 중요하다.

---

점화식

점화식

코드

#include <iostream>
using namespace std;


int main()
{
	// 1,2,3의 합으로 4를 만드는 모든 경우의 수
	
	// 문제를 보고, 작은 것부터 만들어나가 큰것을 구해야 겠다는 생각을 함.
	// 왜?? 
	// 처음에 조합으로 할까? 생각했지만, 중복을 허용하므로 안됨. 
	// 재귀로 할까도 생각했는데, 복잡할 듯 함.

	// => 결론 : d[n] = d[n -1] + d[n -2] + d[n -3]

	// - 7를 만드는 모든 경우의 수 : 44? 
	// 24 13 7 
	// - 6를 만드는 모든 경우의 수 : 24
	// d[5] +  d[4] + d[3]  

	// - 5를 만드는 모든 경우의 수 : 13
	// d[4] +  d[3] + d[2]  
	// - 4를 만드는 모든 경우의 수 : 7개 
	// d[3] + d[2] + d[1]
	// - 3을 만드는 모든 경우의 수.: 4개
	// 1 ,1,1 / 1,2 / 2,1 / 3
	// - 2를 만드는 모든 경우의 수 : 2개
	// 1 ,1 / 2
	// - 1을 만드는 모든 경우의 수 : 1개
	// 1
	// 0을 만드는 모든 경우의 수 : 공집합 -> 1

	int n;
	cin >> n;

	int dp[12]{ 0, };

	dp[0] = 1;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 4;

	for (int i = 3; i <= 11; ++i)
	{
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
	}

	for (int i = 0; i < n; ++i)
	{
		int mm;
		cin >> mm;
		cout << dp[mm] << endl;
	}
}