[BOJ] 18233 : 러버덕을 사랑하는 모임 - travelbeeee

문제 : https://www.acmicpc.net/problem/18233

---

[ 알고리즘풀이 ]

대단한 기법이 쓰인 건 아니지만, 알고리즘을 설계하는데 애를 먹었던 문제입니다.

먼저 backtracking 기법을 이용해서 N 명에서 P 명을 뽑습니다.

그리고 뽑힌 P 명의 최소 인형 수와 최대 인형 수를 다 더해 minimum, maximum 을 구합니다.

minimum <= E <= maximum 이 성립한다면 우리가 가진 인형 E개를 현재 뽑힌 P명에게 줄 수 있다는 것을 의미합니다.

그 후, P명에게 E개의 인형을 나눠주는데 먼저 P명에게 각자 최소 인형 수 만큼 인형을 나눠주고,

남은 인형( E - minimum ) 개를 추가로 나눠주면 문제를 해결할 수 있습니다.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

bool flag = false;
int N, P, E, x, y, ans[20] = {};
vector<pair<int, int>> v;

void back_tracking(int i, vector<int> bt) {
	if (flag)
		return;
	if (bt.size() == P) {
		int minimum = 0, maximum = 0;
		for (int j = 0; j < P; j++) {
			minimum += v[bt[j]].first;
			maximum += v[bt[j]].second;
		}
		if (minimum <= E && E <= maximum) {
			for (int j = 0; j < P; j++) {
				ans[bt[j]] = v[bt[j]].first;
			}
			int temp = E - minimum;
			for (int j = 0; j < P; j++) {
				if (v[bt[j]].second - v[bt[j]].first <= temp){
					ans[bt[j]] += (v[bt[j]].second - v[bt[j]].first);
					temp -= (v[bt[j]].second - v[bt[j]].first);
				}
				else {
					ans[bt[j]] += temp;
					temp = 0;
				}
			}
			for (int i = 0; i < N; i++)
				cout << ans[i] << ' ';
			flag = true;
			return;
		}
	}
	for (int j = i + 1; j < N; j++) {
		bt.push_back(j);
		back_tracking(j, bt);
		bt.pop_back();
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> P >> E;
	for (int i = 0; i < N; i++) {
		cin >> x >> y;
		v.push_back(make_pair(x, y));
	}
	for (int i = 0; i < N; i++) {
		vector<int> bt;
		bt.push_back(i);
		back_tracking(i, bt);
		bt.pop_back();
	}
	if(!flag)
		cout << -1;
	return 0;
}

---