[BOJ_14501] 퇴사

재귀를 이용한 브루트 포스 문제입니다.

 

N+1일째 되는 날 퇴사를 해야하는데, 남은 N일 동안 최대한 많이 상담하여 얻을 수 있는 이익을 구해야 합니다.

우선 Ti와 Pi가 있는데 각각 상담을 하는 데 걸리는 시간과 상담으로 인해 얻는 이익을 의미하는 일차원 배열입니다.

 

재귀로 풀려면 재귀 함수를 구현해야 하는데 이는 우선 정답을 찾은 경우, 찾지 못하는 경우, 그 다음 케이스(재귀)로 구현됩니다.

 

먼저 정답을 찾은 경우는 n+1일이 되는 경우입니다. 이 경우 반환되는 값이 기존의 이익(profit)보다 더 높을 경우 갱신하고 종료(return;)해 줍니다.

 

그리고 다음 분기는 정답을 찾지 못하는 경우입니다. 이 경우는 그냥 종료하는데 바로 day가 n+1을 초과할 때 입니다.

 

마지막으로 다음 경우를 호출할 때 입니다. 상담을 하는 경우와 하지 않는 경우 두 번 호출해 줍니다.

• 상담을 하는 경우 : go(day+t[day], sum+p[day])
• 상담을 하지 않는 경우 : go(day+1, sum+0)

그냥 별다른 처리 없이 함수만 두 번 호출해서 조금 의아할 수 있지만 이러면 재귀를 도는 과정에서 알맞은 케이스를 다 적용해서 최대 profit을 얻을 수 있고 출력하면 됩니다.

 

정말 간단한 재귀 문제였습니다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n;
int profit = 0;
int t[16];
int p[16];
void go(int day, int sum) {
	if (day == n + 1) {
		if (profit < sum)
			profit = sum;
		return;
	}
	if (day > n + 1) {
		return;
	}
	go(day + 1, sum);
	go(day + t[day], sum + p[day]);
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t[i] >> p[i];
	}
	go(1, 0);
	cout << profit << '\n';
	return 0;
}

 

 

14501번: 퇴사 (acmicpc.net)

14501번: 퇴사