[백준] 14501번: 퇴사 - java

문제

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

14501번: 퇴사

 

접근법

DP를 사용해 풀었다.

 

점화식

점화식을 만드는게 어려웠다. 처음엔 dp[i] = i일까지의 누적 최대 이익 이라고 세우고 풀어봤지만 잘 풀리지 않아서 아래와 같이 고쳐서 풀었다.

dp[i] = i일부터 퇴사일까지의 최대 이익

즉, 구하고자 하는 것은 dp[1]인 것이다. 따라서 dp 값을 마지막부터 1까지 구해야된다. 

 

1일에 시작한 상담은 4일에 끝나기 때문에 1일부터 퇴사일까지 얻을 수 있는 최대 이익은 P[1] + dp[4]이다. 이 내용을 토대로 점화식을 좀 더 자세히 세워보자.

dp[i] = P[i] + dp[i + T[i]]

 

하지만 2일 또는 3일에 상담을 시작했을 때 더 큰 이익을 얻을 수도 있다. 따라서 dp[1]의 값은 1일에 시작하는 상담과, 2일에 시작하는 상담의 이익을 비교해야 한다. (dp[2]를 구하는 과정에서 다음 날인 3일과 비교할 것이기 때문에 3일은 비교하지 않아도 된다.)

dp[i] = max(P[i] + dp[i + T[i]], dp[i + 1])

 

점화식을 세웠는데 하나 주의할 점이 있다. 위의 표에서 dp[7] = max(P[7] + dp[9], dp[8])이 된다. 값이 초과되는 것이다. dp[8]은 다음날과 비교하는 것이기 때문에 배열을 하나 더 늘려서 선언해주면 되고, dp[9]와 같이 나머지 상담들도 N을 넘어가는 범위에서 상담이 끝나는 경우가 발생할 수 있으므로 예외처리 하는 코드가 필요하다. 

 

코드

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

public class Main {

    static int N;
    static int[] T;
    static int[] P;
    static int[] dp; // dp[i]: i번째 날부터 퇴사날까지 벌 수 있는 최대 수입

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

        N = Integer.parseInt(br.readLine());

        T = new int[N + 1];
        P = new int[N + 1];
        dp = new int[N + 2];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            T[i] = Integer.parseInt(st.nextToken());
            P[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = N; i >= 1; i--) {
            if (i + T[i] > (N + 1)) {
                dp[i] = dp[i + 1];
            } else {
                dp[i] = Math.max(P[i] + dp[i + T[i]], dp[i + 1]);
            }
        }

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