[BOJ] 백준 12101 1, 2, 3 더하기 2

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

Approach

[BOJ] 9095 1, 2, 3 더하기와 다르게 

정수 N에 대해 1, 2, 3 합으로 이루어진 것을 찾는 문제이다.

[BOJ] 백준 9095 1, 2, 3 더하기

 

오름차순으로 K번째 수식을 찾아야 하는데

DFS로 1→2→3 순으로 수식을 채워가면 오름차순 구성이 가능하다.

순열과 조합을 구하는 문제와 유사하다. → N과 M (4)

순열과 조합 (백준 N과 M 시리즈)

[BOJ] 백준 15652 N과 M(4)

 

DFS 함수에 수식을 이루는 vector와 원소들의 합

- 원소들의 합이 N보타 크면 return

- K번째 수식을 찾은 경우 return

---

#include <iostream>
#include <vector>

using namespace std;

int N, K, cnt;
bool flag;

void DFS(vector<int>& v, int sum)
{
	if (sum > N) return;
	if (flag) return;
	if (sum == N)
	{
		cnt++;
		if (cnt == K)
		{
			for (int i = 0; i < v.size()-1; i++) 
			{
				printf("%d+", v[i]);
			}
			printf("%d\n", v[v.size()-1]);
			flag = true;
		}
		return;
	}
	for (int i = 1; i <= 3; i++) 
	{
		v.push_back(i);
		DFS(v, sum + i);
		v.pop_back(); 
	}
}

int main()
{
	// freopen("input.txt", "r", stdin);
	scanf("%d %d", &N, &K);
	vector<int> v;
	DFS(v, 0);
	if(!flag) printf("-1\n");
}