[백준 BOJ][C++]14501번 퇴사 풀이: 브루트 포스 & 재귀

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

14501번: 퇴사

 

 이 문제는 브루트 포스, 재귀호출을 통해 해결할 수 있습니다. 

 

[풀이 과정]

1. pair<int, int> 타입의 vector arr를 선언한다. (first는 일수, second는 이익)

2. arr에 정보를 입력한다. 

3. arr의 index는 해당 날짜 - 1 을 의미하므로 날짜 + 일수가 n 보다 커지면 계산 X

4. 해당 날짜 + 일수는 다음 날짜를 의미하므로, 재귀함수의 종료조건으로 해당 날짜가 마지막 날짜거나, 다음 날짜가 n보다 같거나 크면 재귀함수를 종료한다. 

5. 다음 날짜부터 n-1 날짜까지 날짜 + 일수가 n 보다 같거나 작다면, 이익을 더해 재귀호출을 한다. 

6. 0일부터 n-1일까지 3~5 과정을 한다. 

 

 

문제에 나타난 예시를 보겠습니다. 

 

index(날짜)	0	1	2	3	4	5	6
first(일수)	3	5	1	1	2	4	2
second(이익)	10	20	10	20	15	40	200

 

0일부터 봅시다!

 

0 + 3 = 3 이므로 n인 7을 넘지 않죠? 그렇다면 첫 번째 관문은 통과입니다. 

 

그렇다면 다음 날짜인 next 는 3일이 됩니다. 우리는 최대 이익값을 구해야하기 때문에 3일부터 6일까지 모든 날짜에 대해 날짜 + 일수가 조건에 맞다면, 재귀호출을 해야합니다. 

 

다음 날짜가 3일일때 재귀호출은 다음과 같이 이루어지겠죠?

index(날짜)	0	1	2	3	4	5	6
first(일수)	3	5	1	1	2	4	2
second(이익)	10	20	10	20	15	40	200

 

 

다음 날짜가 4일이라면 재귀호출은 다음과 같이 이루어집니다. 

index(날짜)	0	1	2	3	4	5	6
first(일수)	3	5	1	1	2	4	2
second(이익)	10	20	10	20	15	40	200

 

다음 날짜로 5일과 6일은 될 수 없습니다. 날짜 + 일수가 n을 넘기 때문이죠!

 

 

이 과정을 0일부터 6일까지 반복하면 최대 이익값을 얻을 수 있습니다. 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>

using namespace std;

typedef pair<int, int> tp;

int n;
vector<tp> arr;
int ans;

void solution(int idx, int sum) {

	int next = idx + arr[idx].first;

	if (idx == n - 1 || next >= n) {
		ans = max(ans, sum);
		return;
	}
	else {
		for (int i = next; i < n; i++) {
			if (i + arr[i].first <= n)
				solution(i, sum + arr[i].second);
		}
	}

	ans = max(ans, sum);
}

int main(void) {

	cin >> n;

	for (int i = 0; i < n; i++) {
		int t, p;

		cin >> t >> p;

		arr.push_back({ t, p });
	}

	for (int i = 0; i < n; i++) {
		if (i + arr[i].first > n)
			continue;

		solution(i, arr[i].second);
	}

	cout << ans;

	return 0;
}