[Algorithm][C++] BOJ 14501 퇴사

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

14501번: 퇴사

 

풀이 핵심

1. dfs 문제 (회귀 함수로 구현)

 

2. 전달 인자는 현재 날짜, 이전에 추가한 날짜, 현재 돈 총합

void dfs(int day, int post, int sum);

 

3. schedule 배열 생성 (상담에 걸리는 시간, 받을 수 있는 돈 정보 저장)

 

4. 다음과 같이 회귀 함수 구현

...
for (int i = day; i <= N; i++) {
	dfs(i + schedule[i].t, i, sum + schedule[i].p);
}
...

 

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int N;
struct info { int t, p; };
info schedule[16]; // 배열 인덱스 == 날짜
int ans;

void dfs(int day, int post, int sum) {
	// N + 1 인 이유는 마지막 날짜까지 포함에서 확인하기 위함
    // 현재 날짜가 N + 1 보다 크면 이전에 더 해준 것을 뺀다
    if (day > N + 1) {
		int m_day = day - schedule[post].t;
		if (m_day <= N) {
			int m_sum = sum - schedule[post].p;
			if (ans < m_sum) ans = m_sum;
		}
		return;
	}
	if (day == N + 1) {
		if (ans < sum) ans = sum;
		return;
	}	

	for (int i = day; i <= N; i++) {
		dfs(i + schedule[i].t, i, sum + schedule[i].p);
	}
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		int t, p;
		scanf("%d %d", &t, &p);
		schedule[i] = { t,p };
	}
	dfs(1, 0, 0);
	printf("%d", ans);
	return 0;
}

 

 

아쉬운 점

1. 처음에는 마지막 날짜를 확인하지 않아서 틀리게 나왔다

2. 하지만 문제에 제시된 테스트 케이스를 통해서 마지막 날짜를 확인하지 않는 것을 확인해서 쉽게 풀 수 있었다.

3. 쉬운 dfs 문제였다.