[C++] 백준 14501번: 퇴사

문제 링크

14501번: 퇴사

문제 요약

N+1일에 퇴사를 하려고 하는데, 퇴사 전에 최대한 많은 상담을 하려고 한다. 1일부터 N일까지 매일 상담이 존재하고, 각 상담에는 걸리는 기간, 받는 금액이 정해져 있다. 이때, 받을 수 있는 금액을 최대화해야한다.

접근 방법

정말 간단한 브루트포스 알고리즘 문제입니다.

보자마자 완전탐색을 돌리면 된다는 생각을 했습니다. N은 최대 15인 반면에, 제한시간은 2초나 됩니다. 이 문제는 각각의 상담을 수락할지 안 할지에 대한 결정의 연속으로 이루어져 있습니다. 따라서 문제를 상태공간트리로 바꿔서 생각할 수 있습니다. 이 상태공간트리의 리프노드의 개수는 $2^{15}$개가 됩니다. $2^{15} = 32768$

구현을 위해서는 재귀호출을 두 번 하는 함수를 만들어야 합니다. 하나는 현재 인덱스의 상담을 수락하는 재귀호출, 다른 하나는 수락하지 않는 재귀호출입니다.

수락하는 경우에는, 직전의 상담이 언제 끝나는지를 비교해보고 재귀호출을 하는 것이 필요합니다. 추가적으로, 상담을 수락한다면, 수락한 상담의 끝나는 일자가 N + 1일 이상이 아님을 판단해야 합니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, res, t[16], p[16];

void func(int idx, int day, int pay)
{
	res = max(res, pay);

	if (idx == n + 1)
		return;

	func(idx + 1, day, pay);
	if (day < idx && idx + t[idx] - 1 <= n)
		func(idx + 1, idx + t[idx] - 1, pay + p[idx]);
}

int main(void)
{
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> t[i] >> p[i];

	func(1, 0, 0);
	cout << res;
	return 0;
}