퇴사 (feat. 백준, 14501번)

퇴사
https://www.acmicpc.net/problem/14501

14501번: 퇴사

반응형

// woohyeon.kim
#include <iostream>
#include <algorithm>

using namespace std;

struct Work
{
	int day;
	int money;
};

int N;
Work works[16];
bool visit[16];
int result;

void dfs(int current_day, int total_money)
{
	if (current_day > N)
	{
		result = max(result, total_money);
		return;
	}
	auto idx = current_day;
	for (; idx <= N; ++idx)
	{
		if (!visit[idx] && (current_day + (idx - current_day) + works[idx].day) <= (N + 1))
		{
			visit[idx] = true;
			dfs(current_day + (idx - current_day) + works[idx].day, total_money + works[idx].money);
			visit[idx] = false;
		}
	}
	if (idx > N)
		result = max(result, total_money);
}

int main()
{
	cin >> N;
	for (auto idx = 1; idx <= N; ++idx)
		cin >> works[idx].day >> works[idx].money;
	for (auto idx = 0; idx < sizeof(visit); ++idx)
		visit[idx] = false;

	result = 0;
	dfs(1, 0);
	cout << result << endl;
	return 0;
}
// *&)*@*

요구하는 날짜와 현재 나의 날짜의 흐름만 잘 계산하면 되는 간단한 문제입니다.