백준 15486 - 퇴사 2

문제

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

리뷰

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

위 실버 3의 퇴사 문제로 시작되는 퇴사 시리즈의 두번째 문제이다.
문제 조건은 퇴사1 문제와 같으나, $N$의 범위가 최대 150만으로 증가한 부분이
차이점으로 그리디 방식으로는 주어진 제한 조건을 통과하기가 어려운 구조였다.

로직은 마지막날부터 최대값을 구하기 위해 연산을 수행하며 아래의 과정을 따른다.

• 현재 일에서 가능한 상담 일정이 끝나는 날(next)를 구한다.
• next가 일하는 기간(N)을 넘어갈 경우, 이전까지 계산한 최대값
  (dp[i+1])을 dp[i]로 갱신한다. dp[N]의 경우도 유연하게 처리하기
  위해 모든 배열의 크기를 N+2로 설정하고 next의 제한 조건도 N+1
  초과로 정의하였다.
• 일하는 기간을 넘지 않을 경우, 이전까지의 최대값(dp[N+1])과 현재 상담을
  선택한 경우를 비교하여 dp[i]를 갱신한다.

로직의 시간 복잡도는 단순히 두번의 반복문을 돌리므로 $O(2N)$이 되고 이는
문제의 시간 제한 조건인 2초를 무난히 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;

public class Main {
    static final int MAX = 1_500_000;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = parseInt(in.nextLine());
        int[] times = new int[MAX + 2];
        int[] prices = new int[MAX + 2];

        StringTokenizer st;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(in.nextLine());
            times[i] = parseInt(st.nextToken());
            prices[i] = parseInt(st.nextToken());
        }

        int[] dp = new int[MAX + 2];
        for (int i = N; i > 0; i--) {
            int next = i + times[i];

            if (next > N + 1) {
                dp[i] = dp[i + 1];
            } else {
                dp[i] = Math.max(dp[i + 1], dp[next] + prices[i]);
            }
        }

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

리뷰