백준 9095번 " 1, 2 ,3" 더하기 [Dynamic Programming]

문제

 

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

문제 접근 순서.

 

1. 3가지의 숫자의 조합으로 합을 만들어 특정한 숫자와 같게 만드는 문제이므로 

    일단 DFS 재귀함수 방식과 DP 점화식 방법을 생각함. 

 

2. DFS 방식으로 문제를 접근할 시 시간복잡도가 O(3^n)으로 목표로 하는 숫자가 크면 클수록 시간복잡도가 커 시간 제한에 

    걸릴 확률이 높아진다. 따라서 DP 방법으로 문제 풀이를 한다. 

 

3.

점화식

출처: https://blog.naver.com/PostView.nhn?blogId=vjhh0712v&logNo=221470862600

 

다음과 같은 규칙을 점화식으로 세운다면 dp[i] = dp[i-3] + dp[i-2] + dp[i-1] 으로 규칙성을 세울 수 있다.

 

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

DFS 방식 문제풀이

#include <iostream>
#include <vector>

using namespace std;

void DFS(int& _iCount, int _iCurSum, int _iTargetNumber)
{
	// 1
	if (_iCurSum + 1 == _iTargetNumber)
	{
		_iCount++;
		return;
	}

	else if (_iCurSum + 1 > _iTargetNumber)
	{
		return;
	}

	else 
		DFS(_iCount, _iCurSum + 1, _iTargetNumber);
		



	// 2
	if (_iCurSum + 2 == _iTargetNumber)
	{
		_iCount++;
		return;
	}

	else if(_iCurSum + 2 > _iTargetNumber)
	{
		return;
	}

	else 
		DFS(_iCount, _iCurSum + 2, _iTargetNumber);




	// 3
	if (_iCurSum + 3 == _iTargetNumber)
	{
		_iCount++;
		return;
	}


	else if (_iCurSum + 3 > _iTargetNumber)
	{
		return;
	}

	else
	{
		DFS(_iCount, _iCurSum + 3, _iTargetNumber);
	}

}


int main()
{
	//1,2,3합으로 만들어라 

	int i_inputCount = 0;
	int i_TargetNumber = 0; 
	int i_Count =0; 
	cin >> i_inputCount; 

	vector<int> m_vecTarget; 


	for(int i=0; i< i_inputCount; i++)
	{
		cin >> i_TargetNumber; 
		m_vecTarget.push_back(i_TargetNumber);
	}

	

	// 여기서 이제 판별
	for(auto& iter : m_vecTarget)
	{
		DFS(i_Count, 0, iter);
		cout << i_Count << "\n";

		i_Count = 0; 
	}

	return 0; 
}

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

DP 방식 문제풀이

 

#include <iostream>
#include <vector>

using namespace std;



int main()
{
	int i_inputTestCase = 0;
	int dp[12] = { 0 }; 

	vector<int> m_vecAnswer; 

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

	cin >> i_inputTestCase; ;

	for(int i=0; i<i_inputTestCase; i++)
	{
		int N; 
		cin >> N; 
		for(int i= 4; i<=N; i++)
		{
			dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
		}
		m_vecAnswer.push_back(dp[N]);
	}
	
	for(auto& iter : m_vecAnswer)
	{
		cout << iter << "\n";
	}


	return 0; 
}