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

 

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

---

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

 

 

https://cclient.tistory.com/128

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

이 문제 연장선이다. 별로 어렵지 않았지만 

꾸역꾸역 넣은 느낌이든다. DFS 이기 때문에 중위순회로 되어있다. 

위 그림이 이해될지는 .. 모르겠지만 아래 코드 구현은 그림과 같다. +1, +2, +3 을 해주는 경우를 나누고 깊이우선 탐색을 한다. 

노란색의 경로는 덧셈이 결과 4가 되는 경우이지만 3번째가 아니다. 즉 패스 그 다음 a경우로 넘어가게 되는데  vec는 1, 1, 1, 1 에 가장 마지막을 빼주고 다음 경우인 2를 넣어준다. vec 1, 1, 1, 2 

b경우는 트리의 높이가 변할 때 더하는 개수도 달라지기 때문에 pop을 진행해준다.

높이를 변경할 때는 vec가 비어 있지 않을때만 성립한다. 

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

int aResult = 0;
int n, k;
vector<int> vec; 
bool check = false; 

void Func(int pNum, int pTarget)
{
	if (pNum > pTarget)
	{
		vec.pop_back();
		return;
	}
	if (pNum == pTarget)
	{
		aResult++;

		if (aResult == k)
		{
			check = true; 
			for (int a = 0; a < vec.size(); ++a)
			{
				cout << vec[a]; 
				if (a != vec.size() - 1)
					cout << "+";
			}
		}
		vec.pop_back();
		return;
	}

	vec.emplace_back(1);
	Func(pNum + 1, pTarget); 

	vec.emplace_back(2);
	Func(pNum + 2, pTarget);
	
	vec.emplace_back(3);
	Func(pNum + 3, pTarget);

	if(!vec.empty())
	vec.pop_back();
}

int main(void)
{

	cin >> n >> k;

	Func(0, n);

	if (!check)
		cout << -1;

	return 0;
}