[백준] 14501. 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

유형을 모르고 이 문제를 접했다면 그냥 완전탐색으로 풀었을 거 같다. 그러나 dp를 공부하다가 접한 문제이기 때문에 dp로 풀기 위한 방법을 고민했다. 그런데 아무리 생각해도 점화식이 생각나지 않았다.. 결국 다른 사람의 풀이를 살짝 참고했다.

 

포인트는 dp 배열을 뒤에서부터 채워주는 것이다! 앞에서부터 채우는 경우만 생각해서 적당한 풀이가 생각나지 않았는데, 뒤에서부터 채운다고 생각하니 금방 점화식을 생각할 수 있었다. (특정 날짜에 일을 시작하면, 그 일이 끝나는 날짜까지는 다른 일을 하지 못한다. 즉, 일이 끝나는 날짜가 중요하기 때문에 배열을 뒤에서부터 채우는 아이디어를 떠올리면 된다.)

 

따라서 점화식은 다음과 같다.

* dp[i]: i번째 날짜에 일을 시작했을 때 받을 수 있는 최대 이익
* dp[i] = input[i] + max(dp[i번째 날짜에 시작한 일이 끝나는 다음 날] ~ dp[n])

 

예를 들어, n이 5이고 각 날짜에 잡혀있는 상담이 다음과 같다고 가정하자.

	1일	2일	3일	4일	5일
걸리는 시간	1	2	3	4	5
받을 수 있는 금액	10	20	30	40	50

 

그러면 dp[5]과 dp[4]는 0, dp[3]은 30, dp[2]는 20 + max(dp[4], dp[5]), dp[1]은 10 + max(dp[2] ~ dp[5])가 된다. 

이때 주의할 점은 dp[1]의 경우 10 + dp[2]가 아니라 10 + max(dp[2] ~ dp[5])라는 것이다. 

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

import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[] dp;
    static int[][] input;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dp = new int[n + 2]; // 배열의 범위는 0 ~ (n + 1), 이때 n + 1은 퇴사하는 날
        input = new int[2][n + 2];

        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            input[0][i] = Integer.parseInt(st.nextToken());
            input[1][i] = Integer.parseInt(st.nextToken());
        }

        int max = 0;
        for (int i = n; i >= 1; i--) {
            int time = input[0][i];
            int revenue = input[1][i];
            int next = i + time; // i번째 날짜에 일을 시작하고 끝난 다음 날짜
            if (next <= n + 1) {
                int availableMaxRevenue = 0; // i번째 날짜에 일을 하고, 그 다음 일들을 할 때 최대 수익
                for (int j = i + time; j <= n; j++) {
                    availableMaxRevenue = Math.max(availableMaxRevenue, dp[j]);
                }
                dp[i] = revenue + availableMaxRevenue;
                max = Math.max(max, dp[i]);
            }
        }

        System.out.println(max);
    }
}

dp 점화식이 생각나지 않으면 뒤에서부터 접근하는 것도 고려해보자.