[코드트리] 외주 수익 최대화하기

문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/max-of-outsourcing-profit/description?page=1&pageSize=20

💻 문제 풀이 : C++

// 고민되는 점?
// 겹치는 기간 판단
// 15개의 O/X를 판단?
// 1번 외주 ... O/X (판단 지표 - 겹치는 기간)
// 2번 외주 ... O/X (판단 지표 - 겹치는 기간)
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

struct Period {
	int time;
	int reward;
};

int n, maxAns;
vector<int> selected;
vector<Period> vacation;

int isGoodDay()
{
	for (int i = 0; i < n; i++)
	{
		if (selected[i] == 1)
		{
			if (i + vacation[i].time > selected.size()) return 0;
			for (int j = 1; j < vacation[i].time ; j++)
			{
				if (selected[i + j] == 1)
				{
					return 0;
				}
			}
		}
	}
	return 1;
}

void dfs(int depth) {
	if (depth >= n) {
		int sum = 0;
		if (isGoodDay())
		{
			for (int i = 0; i < n; i++)
			{
				if (selected[i] == 1)
					sum += vacation[i].reward;
			}
			maxAns = max(maxAns, sum);
		}
		int debug = 0;
		return;
	}

	for (int i = 0; i <= 1; i++)
	{
		selected.push_back(i);
		dfs(depth + 1);
		selected.pop_back();
	}
}

int main()
{
	cin >> n;
	
	// vacation.push_back({ 0, 0 });
	for (int i = 0; i < n; i++)
	{
		int s, e;
		cin >> s >> e;
		vacation.push_back({ s, e });
	}

	dfs(0);

	int debug = 0;

	cout << maxAns << endl;

	return 0;
}

📌 memo 😊