[Baekjoon Online Judge] 14501번: 퇴사

14501번: 퇴사

요구사항

 - 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

 - 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

 - 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

 

N = 7인 경우에 다음과 같은 상담 일정표가 입력으로 주어졌다고 가정한다.

	1일	2일	3일	4일	5일	6일	7일
Ti	3	5	1	1	2	4	2
Pi	10	20	10	20	15	40	200

 

 - 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

 - 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

 - 퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구한다.

입력

 - 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

 - 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

---

위 예시를 살펴보면, 6일 7일의 경우 T6, T7의 일수가 근무 할 수 있는 일수를 넘어서기 때문에 상담 일정을 잡을 수 없다. 최소한 5일에 잡혀있는 상담부터 진행 할 수 있다.

 

4일의 상담 소요 시간은 1일이다. 당일에 끝낼 수 있다. 4일과 5일을 진행하면 총 얻을 수 있는 수익은 20 + 15로 35이다.

 

3일의 상담 소요 시간은 1일이다. 당일에 끝낼 수 있다. 3일, 4일, 5일을 진행하며 총 얻을 수 있는 수익은 20 + 15 + 10으로 45이다.

 

2일의 상담 소요 시간은 5일이다. 즉 7일 부터 다시 상담이 가능하다. 7일은 소요 시간이 2일이기 때문에 상담을 진행 할 수 없다. 결국 얻을 수 있는 수익은 0 + 20으로 20이 된다. 이렇게 되면 차라리 상담을 진행하지 않고 3, 4, 5일을 진행하는 수익이 더 높게 된다.

 

1일의 상담 소요 시간은 3일이다. 즉 4일 부터 다시 상담이 가능하다. 4일 부터 얻을 수 있는 수익은 위에서 구했던 대로 35이다. 1일의 수익은 10이다. 35 + 10은 45의 수익을 얻을 수 있다.

 

결국 1일 4일 5일 상담일은 하면 45의 수익을 얻을 수 있고, 3일 4일 5일 상담을 해도 45의 수익을 얻을 수 있다. 이것을 dp 테이블에 정리하였다.

 

	1	2	3	4	5	6	7
dp	45	45	45	35	15	0	0

 

중점적으로 살펴볼 부분은 상담을 안할 수도 있다는 것이다. 상담을 안하면 이전까지 받을 수 있는 가장 최고의 수익을 유지할 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Baekjoon14501 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine());
        int[] t = new int[n + 1];
        int[] p = new int[n + 1];
        int[] dp = new int[n + 2];

        for (int i = 1; i <= n; i++) {
            String[] input = bufferedReader.readLine().split(" ");
            t[i] = Integer.parseInt(input[0]);
            p[i] = Integer.parseInt(input[1]);
        }

        for (int i = n; i > 0; i--) {
            // 상담을 할 수 있는지 판별하기 위해 상담을 시작 할 수 있는 day를 구한다.
            int day = i + t[i]; 

            // 입력받은 day가 상담할 수 있는 날보다 크게되면 상담을 할 수 없으므로 이전 수익을 유지한다.
            if (day > n + 1) dp[i] = dp[i + 1];  
            // 상담이 가능하면, 이전 수익과 오늘 얻을 수 있는 수익 + day까지 얻을 수 있는 수익을 비교한다. 
            else dp[i] = Math.max(dp[i + 1], p[i] + dp[day]);
        }

        System.out.println(dp[1]);
        bufferedReader.close();
    }
}

---

DFS를 활용한 풀이

다이나믹 프로그래밍이 아닌 DFS를 활용한 방식으로 풀이를 찾아보았다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Baekjoon14501 {
    private static int n, answer = 0;
    private static int[] t, p;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(bufferedReader.readLine());
        t = new int[n + 1];
        p = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            String[] input = bufferedReader.readLine().split(" ");
            t[i] = Integer.parseInt(input[0]);
            p[i] = Integer.parseInt(input[1]);
        }

        dfs(1, 0);
        System.out.println(answer);
    }

    private static void dfs(int day, int value) {

        // day 가 n + 1 이상이 되면 퇴사를 진행한다.
        if (day >= n + 1) {
            answer = Math.max(answer, value);
            return;
        }

        // today 에 상담을 하는 경우 다음 상담 day 는 n + 1 day 를 넘을 수 없다.
        if (day + t[day] <= n + 1) dfs(day + t[day], value + p[day]);
        // today 에 상담을 하지 않는 경우 다음날로 넘어간다.
        if (day + 1 <= n + 1) dfs(day + 1, value);
    }
}

 

상담을 할 때와 안할 때를 기준으로 깊은 탐색을 진행한다. day가 n + 1이 되면 퇴사를 진행하기 때문에 적절하게 return하여 처리해준다.

 

DFS 관련해서는 아직 확실하게 와닿는 느낌이 없어서 지속적으로 DFS에 대한 공부를 해야 할 것 같다.