BOJ 14501. 퇴사

문제 요약

오늘부터 N일 동안 날마다 상담이 하나씩 잡혀 있고, i일의 상담은 T[i]일이 걸리며 끝내면 P[i]를 받는다. 상담을 하는 동안에는 다른 상담을 할 수 없고, N+1일째에는 퇴사하므로 그 전에 끝나지 않는 상담은 할 수 없다. 이 조건에서 고를 수 있는 상담 조합의 최대 수익을 구한다.

---

1. 문제 해석

• N+1일이 되는 날 퇴사를 하려고 한다(1≤N≤15) • 남은 N일동안 최대한 많은 상담을 하려고 한다 • 하루에 하나의 상담을 할 수 있고 • i일에 상담을 하면,T[i]일이 걸리고 P[i]원을 번다

좀 극단적인 예를 들어보면 N=5일때 다음과 같다.

	1일	2일	3일	4일	5일	6일
Ti	3	1	2	2	100	퇴사
Pi	2	5	3	3	10억	-
상담o	o	o	o	o	o	-
상담x	x	x	x	x	x	-

이 경우에 만일 5일의 상담을 한다면 10억을 벌 수 있다. 하지만 6일째 되는 날 퇴사를 해야하므로, 5일에 상담을 하는 것은 불가능하다. 이런 문제는 ‘어떻게해야 최대 수익을 낼 수 있을까?’로 접근하면 다소 어려울 수 있다. 가장 간단한 해결 방법은 ‘어떻게해야 모든 경우를 구해볼 수 있을까?’로 접근해서 모든 경우마다 총 상담비용을 구해서 최종적으로 최댓값을 구하면 될 것이다.

상담을 하거나, 하지 않는 경우로 나누어서 각 날짜마다 선택한다면 2^N의 경우가 생긴다. 따라서 시간복잡도는 O(2^N)이므로 충분히 풀 수 있다.

<hr />

---

2. 문제 풀이

N+1일이 되면 퇴사하게 되므로 day를 기준으로 재귀호출의 종료조건을 걸면 될 것이다. 또한, 상담비용을 기록하기 위해서 sum에 그 값을 누적한다.

• go(day,sum) • day일이 되었다. day일에 있는 상담을 할지 말지 결정해야 한다. • 지금까지 얻은 수익은 sum이다.

day를 계속 증가시키면서 정답을 찾거나 불가능한 경우를 제외할 수 있다. 그리고 정답을 찾았다면 그때의 누적된 수익을 sum을 통해 반환할 수 있다. 이 두가지 경우가 아니라면 다음 경우를 실행하기 위해 재귀호출을 해야하는데, 이때에는 두 가지 경우가 있다. 해당 day의 상담을 하거나, 하지 않는 경우이다.

상담을 하지 않는 경우에는 그냥 day+1을 하여 재귀호출 하면된다. 상담을 하는 경우에는 어차피 해당 상담일만큼 다른 상담을 할 수 없으므로, 그냥 그 상담일 만큼 day에 더해준다.

• 정답을 찾은 경우 • day == n

• 불가능한 경우 • day > n

• 다음 경우 • 상담을 한다 : go(day+t[day], sum+p[day]) • 상담을 하지 않는다 : go(day+1, sum)

#include <iostream>
using namespace std;

int T[21], P[21], N;
int ans = 0;

void go(int day, int sum) {	// day일에 sum만큼의 수익
    if (day == N+1) {		// N+1일이 되면 정답을 찾을 경우이므로 ans=sum후 종료
        if (ans < sum) ans = sum;
        return;
    }
    if (day > N+1) {		// N+1일 보다 커지면 불가능한 경우이므로 종료
        return;
    }
    go(day+1, sum);		// 상담을 하지 않고 하루가 지나는 경우
    go(day+T[day], sum+P[day]);	// 해당 상담을 하는 경우
}

int main() {
    cin >> N;
    for (int i=1; i<=N; i++) {
        cin >> T[i] >> P[i];
    }
    go(1, 0);
    cout << ans << '\n';
    return 0;
}