2018-04-09-3.md

문제

• 백준 온라인저지 14501번 - 퇴사
• https://www.acmicpc.net/problem/14501

풀이

• DFS를 통해서 해당하는 상담을 "한다" or "하지 않는다"로 모든 경우들을 완전탐색을 진행하면서 최댓값을 찾는다.

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int t[100];
int p[100];
int ans = 0;

int get_max(int a, int b){
	return (a<b) ? b : a;
}



void dfs(int day, int sum){

	if(day == n+1){
		ans = get_max(sum, ans);
		return;
	}

	//상담 진행
	if(t[day] + day -1 <= n){
		dfs(day+t[day], sum+p[day]);
	}

	//상담 미진행
	dfs(day+1, sum); 

}

int main (){

	cin >> n;


	for(int i=1; i<=n; i++){
		cin >> t[i] >> p[i];
	}

	//dfs(1,0);
	dp_1();

	cout << ans << '\n';

	return 0;
}

반성

• 그리디 알고리즘을 통한 완전탐색을 시도하였으나 현재에서 최선을 선택하더라도 나중에 뒤에 더 크게 보수를 받을 수 있는 경우의 수가 있어서 그리디 알고리즘은 적절하지 않다.

기타

참고자료