[백준][Java] 15486 - 퇴사 2

목차

 

문제 정보

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

15486번: 퇴사 2

난이도 : G5

유형 : DP

시간 : O(N)

 

---

문제 풀이

n이 1,500,000 이여서 시간초과를 피하기 위해 O(N) 이하로 풀어내야 한다.

따라서 일차원 배열을 이용한 DP로 해결을 했다.

 

1일부터 시작하여 N일까지 순차적으로 DP테이블을 갱신해줬다

 

dp배열은 N+1만큼 선언해 주고

dp[0] = 0으로 초기화

 

점화식)

dp[i + T[i] -1] = Math.max( dp[i + T[i] - 1] , i일차 이전까지의 최대값 + P[i] )

i일에 시작하는 상담이 끝나는 날짜  =  (i일에 시작하는 상담이 끝나는 날짜의 dp값) vs (i일 이전까지의 dp최댓값 + i일에 시작하는 상담의 보수)

 

또한 마지막날에 상담을 끝내지 못하는 경우가 있으면 dp[N]이 갱신될 수 없는 경우가 생기기 때문에 반복문을 돌 때마다 

따로 정답의 최댓값을 기억하고 있어야 한다.

---

코드

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

public class Main {

    private int N;
    private int[] dp;
    private int T, P;
    private int max;
    private int res;

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];

        max = 0;
        res = 0;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            T = Integer.parseInt(st.nextToken());
            P = Integer.parseInt(st.nextToken());

            max = Math.max(max, dp[i - 1]);

            if (i + T - 1 <= N) {
                dp[i + T - 1] = Math.max(dp[i + T - 1], max + P);
                res = Math.max(res, dp[i + T - 1]);
            }
        }
        System.out.println(res);
    }

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }
}