[C++][백준] 14501번 퇴사 :: seoftware

 

---

 

소스코드

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int arr[15][2];
int answer;
void getNext(int day, int &sum) { 
	
	bool stop = true;
	for (int i = day; i < N; i++) {
		if (i + arr[i][0] <= N) {
			sum += arr[i][1];
			getNext(i + arr[i][0], sum);
			sum -= arr[i][1];
			stop = false;
		}
	}
	if (stop) {
		if (answer < sum) answer = sum;
		return;
	}
}
int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i][0] >> arr[i][1];
	}
	for (int i = 0; i < N; i++) {
		if (i + arr[i][0] <= N) {
			int sum = arr[i][1];
			getNext(i + arr[i][0], sum);
		}
	}
	cout << answer << endl;
}

 

1. [main 함수] 2차원 배열 arr에 T와 P를 입력을 받는다.

2. [main 함수] 모든 T를 시작점으로 하여 getNext() 함수를 이용하여 다음을 구한다.

3. [getNext 함수] day와 sum을 인수로 한다. day를 시작 인덱스로 하여 for문을 돈다. sum에 현재 for문의 P를 더해주고, 다시 getNext() 함수를 호출한다. getNext의 인자 중 day를 다음 일을 할 수 있는 날짜(i+T(i))로 준다. 

4. [getNext 함수] 추가 될 수 있는 날이 없는 상황이 되면 stop 플래그가 바뀌지 않으므로, 그 때 return 한다.