[백준 알고리즘][DFS] 14501번 퇴사

문제 정의

N+1일째 되는 날 퇴사하기 위해서 남은 N일 동안 최대한 상담을 많이해서 얻을 수 있는 이익을 구하는 문제이다. 매일 하루의 상담일정이 있는데 각 상담에 소요되는 기간이 다르기 때문에 가장 많은 이익을 가져다주는 상담일정을 짜야한다.

문제출처: 백준 온라인 저지(https://www.acmicpc.net/problem/14501)

문제 풀이

이 문제도 이전에 풀었던 문제와 마찬가지고 N이 15보다 작기때문에 완전탐색을 통해 모든 경우를 탐색해봐야 한다. DFS를 수행해서 여러가지 경우를 탐색해보면 될 것 같다. i번째 날의 상담을 하게 된다면 i일로부터 T[i]일 이후의 상담으로 탐색해야한다. 이런식으로 DFS+백트래킹을 통해서 모든 경우의 수익을 계산하고 최대 수익을 저장하도록 한다.

(+ 2018.9.21) 오랜만에 다시 DFS로 풀어보는데 생각보다 잘 안 풀렸다. 예외케이스가 있었는데 DFS 탐색할 때에는 curr+T[curr] 이후의 날들만 살펴보면 되지만 마지막 N번째 날이 되었을 때 하루 만에 끝날 수 있으면 해당 이익을 추가해줘야 하는 부분이 효율적으로 구현하기 애매해서 이리저리 수정을 해봤다. 3월에 이 문제를 풀 때는 visited 를 둬서 DFS에서 마지막 노드?에 도착했을 때 다시 O(N)을 통해서 이익을 구하도록 구현했는데 새로 풀면서 그렇게 하지 않고 탐색할 때에 이익을 더해오다가 마지막에는 마지막 노드의 이익을 추가해줄 것인지 아닌지만 결정하여 max값을 갱신시켜주도록 새로 구현해봤다. 이 문제에서는 N이 15이하라서 괜찮은데 N이 꽤 큰 값일 때에는 바로 계산을 해주는 것이 나은 것 같다. 

코드

void DFS(int curr)

{

int i, j;

int val;

if(curr + T[curr] >= N){

if(curr+T[curr] == N)

val = P[curr];

else 

val = 0;

for(j=0;j<N; j++)

{

if(visited[j] == 1)

val += P[j];

}

result = max(result, val);

return ;

}

else

visited[curr] = 1;

for(i = curr+T[curr]; i<N; i++)

{

DFS(i);

}

visited[curr]=0;

}