백준 14501 - 퇴사

문제링크

• 백준 14501

문제 설명

• 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
• 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
• 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
• 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

 	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200
1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

• 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
• 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
• 또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
• 퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
• 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

문제 접근

• 재귀호출을 통해 현재 날짜의 상담을 진행하는 경우와 진행하지 않는 경우 중 최종 이익이 가장 큰 경우를 찾는 방법을 생각했다.

구현

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

int N;
vector<int> timeTable;
vector<int> priceTable;

int search(int day, int profit)
{
	if (day > N) {
		return profit;
	}
	int nextDay = day + timeTable[day -  1];
	int curProfit = profit;
	if (nextDay <= N + 1) curProfit += priceTable[day - 1]; // 상담 진행할 경우 이익
    // max(상담을 진행하는 경우, 상담을 진행하지 않는 경우)
	return max(search(nextDay, curProfit), search(day + 1, profit));
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> N;
	for (int day = 1; day <= N; day++) {
		int time, price;
		cin >> time >> price;
		timeTable.push_back(time);
		priceTable.push_back(price);
	}
	cout << search(1, 0) << endl;
}