84. 휴가(삼성 SW역량평가 기출문제 : DFS 활용) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★

 

#include <stdio.h>
#include <vector>

using namespace std;

int n, t, p, money = 0;
struct COS
{
	int day;
	int cost;
	
	COS(int x, int y)
	{
		this -> day = x;
		this -> cost = y;
	}
};

vector<COS> v;

void DFS(int x, int y)
{
	if(x == n+1) // n+1부터 휴가이므로
	{
		if(y > money) money = y;
	}
	else
	{
		COS temp = v[x]; // 해당 일차의 드는 시간과 받는 돈
		if(x + temp.day <= n+1) DFS(x + temp.day, y + temp.cost); // 상담을 하겠다
		DFS(x + 1, y); // 상담하지 않겠다, 언젠가 n+1과 만나 끝나게 되어있음
	}
}

int main()
{
	scanf("%d", &n);
	
	v.push_back(COS(0, 0)); // 벡터의 0번째는 사용하지 않기 위해 임의 값 할당(1일차부터 시작이기 때문)
	
	for(int i = 1; i <= n; i++)
	{
		scanf("%d %d", &t, &p);
		v.push_back(COS(t, p));
	}
	
	DFS(1, 0); // 1일부터 시작
	
	printf("%d", money);
	
	return 0;
}