백준 14501 퇴사

DFS로 해결가능 한 문제이다.

하지만 다른 분들이 푼 방식을 보니 DP를 사용하였더라.

DFS로 단순히 탐색을해서 푼것보다 분명 DP를 사용해 푸는것이 시간적인 면에서 훨씬 효율적일 거란 생각이 든다.

우선 내가 푼 방식은

1일째부터 차례대로 dfs로 탐색을 해준다.

표에 있는 예제대로 진행한다면, 1일에 일을 했따면 4일부터 가능하다. 4일에 일을 할 수 있는지 판단하고 다시 dfs로 진행한다.

이처럼 매번 해당 일이 N+1의 마감일을 넘지 않는지 확인해 준다.

1일부터 시작했다면 2일부터 시작을 또 해줘야한다. 그렇게 3,4,5,6,7일을 "시작으로" 탐색을 시작한다.

왜냐하면 저 예제에서는 1일부터 하는 것이 최적의 답이겠지만, 다른 경우가 충분히 있을 수 있기 때문이다 !!

dfs에서 V[i]를 false로 셋팅을 다시 해주지 않으니 틀렸었다 아마 다른 반례에서 탐색 경로가 꼬여 답이 틀렸는 것 같다.

코드:

#include <iostream>

using namespace std;

int n,t,p,ans;

struct input{

int t;

int p;

};

bool V[16];

struct input a[16];

void init(){

for (int i = 0; i <= n; i++){

V[i] = false;

}

}

int dfs(int start){

int ret = 0;

int tmp = 0;

if (start + a[start].t > n + 1) return 0;

V[start] = true;

for (int i = start + a[start].t; i <= n; i++){

if (!V[i]){

tmp = dfs(i);

if (tmp > ret) ret = tmp;

}

}

V[start] = false;

return ret + a[start].p;

}

int main(){

cin >> n;

for (int i = 1; i <= n; i++){

cin >> t >> p;

a[i].t = t;

a[i].p = p;

}

for (int i = 1; i <= n; i++){

int tmp = dfs(i);

if (ans < tmp) ans = tmp;

init();

}

cout << ans;

//system("pause");

return 0;

}

** 다른 사람들이 푼 DP방식은 간단해 보이니, 차후에 직접 DP 점화식을 세워보는 것으로!