[백준] 퇴사 (C++)

#include <iostream>
#include <algorithm>

using namespace std;
/*
오늘부터 남을 N일 동안 최대한 많이 상담일 함
얻을 수 있는 최대 수익 출력
*/
struct day {
	int t;  //소요시간
	int p;  // 수익
};

day arr[20];
int answer = 0;
int n;

void dfs(int idx, int sum) {
	if (idx >= n) {
		answer = max(answer, sum);
		return;
	}
	//상담 안할 경우
	dfs(idx + 1, sum);
	//상담 할 경우 (상담해도 되는지 조건 확인)
	if (idx + arr[idx].t <= n)
		dfs(idx + arr[idx].t, sum + arr[idx].p);
}

int main() {
	freopen("input.txt", "r", stdin);
	cin.tie(0);

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

	dfs(0, 0);

	cout << answer << endl;
	return 0;
}

배열의 길이가 작아서 반복문으로 풀었다가 틀렸던 문제,,

재귀 함수로 풀었으며 1. 상담을 할 경우와 2. 상담을 안 할 경우 두 가지 케이스로 나누어서 풀어야한다.

 

케이스를 나누어서 재귀 함수로 푸는 방법을 생각할 수 있도록 해야겠다.