[백준] 14501번 퇴사

14501번: 퇴사

입력이 N (1 ≤ N ≤ 15)라길래 브루트포스로 풀었다.

조합은 시간 복잡도가 계승(팩토리얼)함수이기  때문에 n이 20 정도만 돼도 답을 구하기가 힘들다.

따라서 입력이 1 ≤ N ≤ 15 이라는 것을 보고 힌트를 얻었다. 마음놓고 조합으로 풀어도 된다는 것이구나.

 

조합(Combination)으로 N개 중 1개를 고르는 경우부터 N개를 고르는 경우까지 모든 경우를 다 구하고

그러고 나서 나중에 조건을 체크했다.

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

int** arr;
int n;
vector<int> profit;

void select(vector<bool> visited, vector<tuple<int, int, int>> result, int theNumberOfSelect, int num) {

	if (num == theNumberOfSelect) {

		int total = 0;
		if (get<2>(result[0]) + get<0>(result[0]) > n) {
			return;
		}
		for (int i = 1; i < theNumberOfSelect; i++) {
			if (get<2>(result[i]) + get<0>(result[i]) > n) {
				return;
			}
			if (get<2>(result[i - 1]) + get<0>(result[i - 1]) > get<2>(result[i])) {
				return;
			}
		}
		for (int i = 0; i < theNumberOfSelect; i++) {
			total += get<1>(result[i]);
		}

		profit.push_back(total);
		return;
	}
	for (int i = 0; i < n; i++) {
		if (num != 0) {
			if (get<2>(result[num - 1]) < i) {
				if (!visited[i]) {
					visited[i] = true;
					result[num] = make_tuple(arr[i][0], arr[i][1], i); //걸리는 기간, 받는 금액, 시작 날짜
					select(visited, result, theNumberOfSelect, num + 1);
					visited[i] = false;
				}
			}
		}
		else {
			if (!visited[i]) {
				visited[i] = true;
				result[num] = make_tuple(arr[i][0], arr[i][1], i); //걸리는 기간, 받는 금액, 시작 날짜
				select(visited, result, theNumberOfSelect, num + 1);
				visited[i] = false;
			}
		}
	}
}

int main() {
	cin >> n;
	arr = new int*[n];
	for (int i = 0; i < n; i++) {
		arr[i] = new int[2];
	}
	for (int i = 0; i < n; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	for (int i = 0; i < n; i++) {
		vector<tuple<int, int, int>> result(i + 1);
		vector<bool> visited(n);
		for (int j = 0; j < n; j++) {
			visited[i] = false;
		}
		select(visited, result, i + 1, 0);
	}
	int maxProfit = 0;
	for (int i = 0; i < profit.size(); i++) {
		if (profit[i] > maxProfit) maxProfit = profit[i];
	}
	cout << maxProfit;
	return 0;
}