(백준/ C++) 9095 - 1, 2, 3 더하기 / 다이나믹 프로그래밍, 재귀

 

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

---

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

 

문제 보자 마자.. 음 ? 재귀 ? 했고, n은 11보다 작은 양수였다. dp로 안 풀어도 되는 문제 아닌가 생각했다. 

아래와 같이 어떠한 방법이든 합이 N이 되면 되기 때문에 N이 되면 결과값을 ++ 해주게 코딩 했다. 

개행을 안 붙여서 틀렸었는데 4%에서 틀렸다고 하면 개행 안 붙여서 이다. 

// 9095 - 1,2,3 더하기

#include<iostream>
using namespace std;

int aResult = 0;

void Func(int pNum, int pTarget)
{
	if (pNum > pTarget)
		return;

	if (pNum == pTarget)
	{
		aResult++;
	}

	Func(pNum + 1, pTarget); 
	Func(pNum + 2, pTarget);
	Func(pNum + 3, pTarget);

}

int main(void)
{
	int mTC;

	cin >> mTC;

	while (mTC--)
	{
		int N;
		cin >> N; 

		Func(0, N);

		cout << aResult << endl; 
		aResult = 0; 
	}

	return 0;
}

 

해결하고 나서 다른 사람들의 풀이를 보았다. 

내용은 N의 수가 1, 2, 3, 4, 5, 6, 7 ... 합으로 나타내는 방법의 수가 점화식으로 표현 될 수 있다는 점을 이용한 DP였다. 

1[ 1 ], 2[ 2 ], 3[ 4 ], 4[ 7 ], 5[ 13 ], 6[ 24 ] .... 

a[ n ] = a [ n - 1 ] + a [ n - 2 ] + a [ n - 3 ]  이 전의 조합으로 만든 수에 1,2,3을 각각 더 했을 때 현재의 수가 나오기 때문에 이러한 점화식이 성립이된다. 

빠르게 점화식을 찾았으면 좋지만 n의 수가 적기 때문에 재귀로 풀어도 문제는 없다.