[백준 14501] 퇴사

분류 

dfs

요구사항

최대로 이익을 얻을 수 있도록 상담 날자 정하기

 

풀이

n이 15로 작다.

모든걸 다 탐색 해보면 된다

 

1. 현재 요일 선택안하고 진행할 경우

2. 현재 요일 선택하고 진행할 경우

dfs를 사용하여 두가지를 탐색해본다

 

#include <string>
#include <vector>
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <deque>

using namespace std;

int t[20];
int p[20];
int n;
int ans=0;
void solve(int now, int sum){

	if(now==n+1){
		ans=max(sum,ans);
		return;
	}
	//현재꺼 선택 안함
	solve(now+1,sum);
	//현재꺼 선택
	if(now+t[now] <= n+1){
		solve(now+t[now],sum+p[now]);
	}

}
int main(){
	scanf("%d",&n);
	for(int i=1; i <=n ; i++){
		scanf("%d%d",&t[i],&p[i]);
	}
	solve(1,0);
	cout<<ans<<endl;
}