[백준] 14501번: 퇴사

 

문제 이해

오랜만에 보는 DFS의 인자가 1씩 증가하는 경우가 아닌 문제였다.

어느 날 의뢰받은 업무를 할 것인지를 정하는 모든 경우의 수를 탐색하면 된다.

 

일단 DFS의 인자인 day는 현재 날짜이다. day에서부터 업무를 다시 재개할 수 있다. 즉, day가 6이면 6일자 업무부터 다시 선택할 수 있다는 것이다.

profit은 현재까지 업무를 선택해서 얻은 수익이다.

 

아무튼, day서부터 다시 업무를 뽑을 수 있으므로 재귀부분에서 for문의 시작점이 day가 된다.

 

종료 조건이 조금 헷갈리는데, day > N+1 로 설정한 이유는,

• 만약 day == N이면 (예제1의 경우 7) N(7)일차 업무는 선택할 수 있으니까 선택할 수 있도록 재귀문으로 보내줘야 한다.
• 만약 day == N+1이면 N+1차부터는 회사에 없는 날이라 새로운 업무를 시작할 수 없지만, N일에 하루치 업무를 봤다면 N+1일까지 넘어오고 이건 유효한 업무처리이다. 따라서 profit이 max보다 큰지를 확인하는 if문까지 가야하므로 이 경우에도 패스해줘야 한다.
• 하지만 그 이상 (day > N+1)부터는 업무를 처리할 수 있는 상황(날짜가 지나보림)에서 업무를 처리했다고 친 경우니까 다 return해줘야 한다. 

 

종료 조건 때문에 조금 헷갈렸지만 그냥 전형적인 DFS문제일 뿐이었다

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 15

int N;
typedef struct st {
	int t;
	int p;
}ELE;
ELE A[MAXN+2];
int max;

void Get_Input(void) {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &A[i].t, &A[i].p);
	}
}

void DFS(int day, int profit) {

	// 종료
	if (day > N+1) return; // 여기가 조금 헷갈리는데, 
	// 7일에 업무를 해서 8일이 되었다면 가능하니까, N+1까진 봐줘야 함
	
	if (max < profit) max = profit;

	// 재귀
	for (int i = day; i <= N; i++) {
		DFS(i + A[i].t, profit + A[i].p);
	}

}

int main(void) {
	Get_Input();
	DFS(1, 0);
	printf("%d", max);
	return 0;
}