[백준] 14501번 퇴사 C++ 문제풀이

https://www.acmicpc.net/problem/14501

14501번: 퇴사

문제 풀이

완전탐색 문제여서 모든 경우를 고려했다.

그 날의 상담을 수락하는 경우와 그 날의 상담을 하지 않고 그냥 다음 날로 넘어가는 2가지 경우로 나누어 진행했다.

DFS를 이용해 상담을 수락하는 경우는 상담이 끝나는 다음 날로 이동하고, 아닌 경우는 다음 날로 이동하게 코드를 작성했다.

소스 코드

#include <iostream>
using namespace std;

int money[21] = { 0 };
int day[21] = { 0 };
int N;
int max_num = 0;

void dfs(int d, int m) {
	if (d > N) {
		return;
	}
	else {
		//그날의 일을 하는 경우
		if (d + day[d] <= N + 1) {
			int day_m = money[d]; // 상담 보수
			max_num = max(max_num, m + day_m); 
			dfs(d + day[d], m + day_m); // 그 상담이 끝나는 날로 가서 진행
		}
		//그 날의 일을 하지 않고 그냥 다음 날 업무로 넘어가는 경우
		dfs(d + 1, m);
	}
}


int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> day[i] >> money[i];
	}
	dfs(1, 0);

	cout << max_num << '\n';

}