퇴사

조합 가능한 모든 날짜의 이익을 계산한다. 기저사례 (1) 이미 정한 상담 날짜와 겹치는 상담은 패스 (2) 상담 날짜가 퇴직 날짜를 초과하는 경우 패스 (3) 탐색하는 상담의 시작일이 퇴사날짜를 넘으면 탐색 종료

// index ~ index + T[index]동안 상담이 확정되었을 때, 그리고 현재 이익이 sum일 때 // 그 뒤로 상담 가능한 것을 선택한다. int calc(int index, int sum)

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

int n; // 상담할 수 있는 날짜 수

int ret = 0; 
vector<int> T, P; 

void calc(int index, int sum) {
	if (index == n) {
		if (ret < sum) ret = sum;
		return; 
	}

	for (int i = index + 1; i <= n; i++) {
		// 현재 상담이 끝난 후에 시작되는 상담이고, 
		// 퇴사하기 전에 끝나는 상담이라면
		if (i >= index + T[index] && i + T[i] <= n)
			calc(i, sum += P[i]); 
	}
}

int main() {
	cin >> n;
	T.push_back(0); P.push_back(0); 
	for (int i = 1; i <= n; i++) {
		int num1, num2; cin >> num1 >> num2; 
		T.push_back(num1); P.push_back(num2); 
	}

	for(int i = 1; i <= n; i++)
		calc(i, P[i]);
	cout << ret << endl;
}

여기에 진입하지 않는다. 마지막 인덱스는 주로 재귀호출이 되지 않는데, 그러면 index가 n일 경우가 없어져서 예외처리되지 않는 것이다.

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

int n; // 상담할 수 있는 날짜 수

int ret = 0; 
vector<int> T, P; 

void calc(int previous, int current, int sum) {
	// 현재 상담이 끝나지 않았다면
	if (current < previous + T[previous]) return; 
	// 퇴사한 후에 끝나는 상담이라면
	if (current + T[current] > n) return;
	// 퇴사일이 지났다면
	if (current == n + 1) {
		if (ret < sum) ret = sum;
		return; 
	}
	
	// 이번 상담을 선택하는 경우 
	calc(current, current + 1, sum += P[current+ 1]); 

	// 이번 상담을 선택하지 않는 경우
	calc(current, current + 1, sum); 
}

int main() {
	cin >> n;
	T.push_back(0); P.push_back(0); 
	for (int i = 1; i <= n; i++) {
		int num1, num2; cin >> num1 >> num2; 
		T.push_back(num1); P.push_back(num2); 
	}

	calc(0, 1, P[1]); 
	cout << ret << endl;
}

위 코드는 1일의 상담 일정에 2일자 상담이 겹치므로 두 재귀 호출이 모두 바로 반환되는 문제가 있었다. 결국에는 for문을 써야하는 건가?

해설

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define INF 987654321
using namespace std;

int n; // 상담할 수 있는 날짜 수

int cache[16]; 
vector<int> T, P;

// day일이 되었다. day일에 있는 상담을 할지 말지 결정한다. 
// 지금까지 얻은 수익은 sum이다.
int calc(int day) {
	if (day == n + 1) return 0;
	if (day > n + 1) return -INF;

	int& ret = cache[day];
	if (ret != -1) return ret;

	int t1 = calc(day + 1); 
	int t2 = P[day] + calc(day + T[day]);
	ret = max(ret, max(t1, t2)); 

	return ret; 
}

int main() {
	ios_base::sync_with_stdio(false); 
	cout.tie(NULL); 
	
	memset(cache, -1, sizeof(cache)); 
	cin >> n;
	T.push_back(0); P.push_back(0);
	for (int i = 1; i <= n; i++) {
		int num1, num2; cin >> num1 >> num2;
		T.push_back(num1); P.push_back(num2);
	}
	cout << calc(1) << endl;
	return 0;
}

이 문제는 앞에서 결정한 답들이 뒤에 영향을 미치지 않는다는 특징이 있었다. 따라서 메모이제이션으로 현재 day까지 계산한 합계를 사용할 수 있다.

이 때 day == n + 1이라면 퇴사일이 된거니까 바로 return 0을 해준다. 그리고 재귀호출에서 바로 day + T[day]로 점프하기 때문에 , day > n+1이라면 인덱스 에러가 뜬다. 따라서 -INF를 반환하도록 해준다.