[백준][C++] 14501. 퇴사

n일동안 상담 일정을 적절히 잡아 최대 이익을 구하는 문제이다.

 

처음 문제를 보자마자 생각난 알고리즘은 DP였지만...

효율적인 공식이 생각나지 않아 결국 DFS로 방향을 틀었다.

 

 

일하는 날짜(start), 현재까지의 이익(cur_profit)을 인자로 받고,

start부터 n일까지 dfs를 돌면서 일할 수 있는 모든 경우를 탐색하면 된다.

 

 

딱히 어려운 점은 없었지만,

처음에 start가 n보다 크면 dfs를 종료하도록 코드를 짰다가

마지막 날(n일)에 일하게 되는 경우가 제외되어 최대 이익이 제대로 계산되지 않았다.

 

그래서 start > n + 1로 수정해주었고 결국 맞았다.

 

if (visited[start] || start > n + 1) return; 

 

 

// 14501_퇴사.cpp 
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#include <iostream>
#define DAY 16

int n; // 근무 일수
int T[DAY] = { 0, };
int P[DAY] = { 0, };
int visited[DAY] = { 0, };

int max_profit = 0;
void dfs(int start, int cur_profit) { // start: 시작일, cur_profit: 현재까지의 이익
	// 마지막 날(n일)에 일할 수 있는 경우도 포함되도록 start > n + 1
	if (visited[start] || start > n + 1) return; 
	if (max_profit < cur_profit) max_profit = cur_profit;
	
	for (int i = start; i <= n; i++) {
		if (!visited[i]) {
			visited[i] = 1;
			dfs(i + T[i], cur_profit + P[i]);
			visited[i] = 0; // 백트래킹
		}
	}
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &T[i], &P[i]);
	}

	dfs(1, 0); 
	printf("%d\n", max_profit);

	return 0;
}