[백준] 15486. 퇴사 2

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

15486번: 퇴사 2

지난 번에 푼 퇴사 문제와 동일한데 N의 범위만 커졌다. 따라서 퇴사 문제의 답을 제출하면 시간 초과가 나고, O(N)의 시간 복잡도로 해결해야 한다.

 

코드를 보면 금방 이해할 수 있다. 주요 포인트는 다음과 같다.

• max는 i 날짜까지의 최대 수입을 의미한다.
• i 날짜에 일을 시작하면 일이 끝난 다음날인 nextDay에 돈을 받는다고 가정한다.
• dp[nextDay] = Math.max(dp[nextDay], max + pay[i]) 

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

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

// 시간 복잡도: O(N) = 1,500,000
public class Main {

    static int n;
    static int[] time;
    static int[] pay;
    static int[] dp;

    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];
        time = new int[n + 2];
        pay = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            time[i] = Integer.parseInt(st.nextToken());
            pay[i] = Integer.parseInt(st.nextToken());
        }

        int max = 0; // i 날짜까지의 최대 수입
        for (int i = 1; i <= n + 1; i++) {
            max = Math.max(max, dp[i]);

            int nextDay = i + time[i];
            int pay = Main.pay[i];
            if (nextDay <= n + 1) {
                dp[nextDay] = Math.max(dp[nextDay], pay + max);
            }
        }

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