백준 14501 (퇴사)

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

14501번: 퇴사

풀이

DFS 재귀함수를 사용하여 풀면 되는 간단한 문제이다.

조건을 정리하면 다음과 같다

1. N이 주어지며 N + 1 일째 되는날 퇴사를 한다. 따라서 일을 수행할 수 있는 날은 N일 까지이다

2. 상담시 당일을 포함하여 날짜를 계산 

EX ) 1일에 상담을 실시하며 1일에 수행하는 상담 소요일이 2일 일경우 1, 2 일 이렇게 총 2틀이 소요 됨 따라서 다음 상담은 3일에 가능하다.  따라서 당일 + 상담 소요일을 하면 다음 상담 가능 날짜가 구해진다. 이때 주의를 해야하는 부분이 마지막 날 일 경우이다 만약 N == 7 일 경우 7일째 상담에 소요되는 시간이 하루라면 7 + 1 = 8 이 됨으로 상담 가능 일의 최대는 N + 1 과 같거나 작을때로 가정해야함

#include <iostream>
using namespace std;

int dayList[1500];
int daymn[1500];
int maxDay = 0;
int maxx = 0;

void dfs(int day, int sum){
	if (maxx < sum) maxx = sum;

	for (int i = day; i < maxDay + 1; ++i){
		if (i + dayList[i] <= maxDay + 1){
			dfs(i + dayList[i], sum + daymn[i]);
		}
	}
}

int main(){
	freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> maxDay;

	for (int i = 1; i <= maxDay; ++i){
		cin >> dayList[i] >> daymn[i];
	}

	dfs(1, 0);
	printf("%d", maxx);

}