백준 : 퇴사 c++

www.acmicpc.net/problem/14501

14501번: 퇴사

풀이

1. DFS로 풀었다. 경우는 두가지

 1) 그날에 주어진 일을 한다!

   -> 일을 했으면 이게 끝나는 다음날로 이동!!

 2) 그날에 주어진 날은 안하고 다음날로 넘어간다!

   -> 기존 day에 +1

 

#include <iostream>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
int answer = 0;

vector<pair<int, int> > v;

void dfs(int day, int sum)
{
	if (day > n)
	{
		answer = max(sum, answer);
		return;
	}

	

	//1번경우는 지금 날에 잡혀있는 상담 할때
	if (day + v[day].first-1 <= n)//이 상담을 할 수 있을때!
	{
		dfs(day + v[day].first, sum + v[day].second);
	}

	//2번 경우는 이날 일 안하고 넘기기!
	if (day+1 <= n+1)
	{
		dfs(day + 1, sum);
	}

}

int main()
{
	int a, b;
	cin >> n;
	v.push_back(make_pair(0, 0));//잉여값

	for (int i = 0; i < n; i++)
	{
		cin >> a >> b;
		v.push_back(make_pair(a, b));
		//v[i]의 경우 i+ v[i].first-1 일일때 일이 끝나고
		//v[i].second만큼 금액을 받음
	}

	dfs(1, 0);

	cout << answer << endl;
	return 0;
}