백준 14501 퇴사

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

14501번: 퇴사

<입력>

1. 퇴사까지 남은 날짜

2. 날짜마다 비서가 배정해준 상담의 정보

 2.1 상담에 걸리는 시간(일)

 2.2 상담 완료시 얻는 이익

이 정보로 주어진다.

 

<규칙> 

1. 상담이 진행중인 날에는 추가적인 상담이 불가능하다.

2. 상담의 종료일자가 퇴사날을 넘어가면 상담이 불가능하다.

 

<출력>

퇴사전까지 상담을 통해 얻을 수 있는 최대 이익을 출력한다.

 

무난한 재귀문제로 날짜마다

1. 상담을 진행

2. 진행하지 않고 다음 날짜의 상담 진행

의 경우를 설정해서 다시 함수를 호출해서 진행한다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <memory.h>
#include <utility>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// 1<=n<=15, brute force with recursion

int n, i, x, y;
vector <pair <int, int>> v;

int func(int);

int func(int k) {

	if (k == n) return 0;

	if (v[k].first + k > n) return func(k + 1);
	return max(v[k].second + func(k + v[k].first), func(k + 1));
}


int main(void) {
	
	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		scanf("%d %d", &x, &y);
		v.push_back(make_pair(x, y));
	}

	printf("%d", func(0));

	return 0;
}