[BOJ_14501 | DFS] 퇴사

풀이

맨 처음에는 Dynamic Programming 방법으로 문제를 풀려고 시도했으나, 

문제를 읽고 예제 몇개를 그림으로 그려가면서 시도를 해보니 DFS로 문제를 푸는 편이 더 간편할 것 같다는 생각이 들었다.

DFS로 문제를 푸는 방법은 비교적 간단하다.

큰 틀에서 보면 이중 For 문을 돌리는 것인데, 

제시된 문제 예제를 기준으로 설명해보자면,

1일부터 7일까지 반복문을 돌리면서 각각의 날짜를 시작으로 하는 경로를 찾는다.

그리고 각각의 날짜에서 상담을 수행한 후에, 도달하게 되는 날짜를 다시 DFS에 집어넣어 반복한다.

예를 들어 

1로 시작했다면, 1로 시작할 수 있는 경로는

1 -> 4 ....

1 -> 5 ....

1 -> 6 ....

등이 될 것이다.

이 모든 경로를 탐색하면서 경로에 놓여있는 Pi값을 더해주고

모든 탐색이 끝난 후에 가장 큰 값을 출력해주면 된다.

소스 코드

import java.util.*;
public class BOJ_14501 {
 
    static int[] dp, day, cost;
    static int n, max;
 
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        n = input.nextInt(); dp = new int[n];
        day = new int[n]; cost = new int[n];
 
        max = -1;
        for(int i=0;i<n;i++){
            day[i] = input.nextInt();
            cost[i] = input.nextInt();
        }
        for(int i=0;i<n;i++){ DFS(i, 0);}
        System.out.println(max);
    }
    public static void DFS(int start, int m) {
        if (start+day[start] >= n) {
            if(start+day[start] == n){m += cost[start];}
            if (m > max) max = m;
            return;
        }else {
            for (int i = start + day[start]; i < n; i++) { DFS(i, m + cost[start]); }
        }
 
    }
}