[백준] 15486번 퇴사 2 (JAVA)

문제

- 오늘부터 N+1일째 되는 날 퇴사하기 위해, 남은 N일 동안 최대한 많은 상담을 하려 함

- 각각의 상담은 상담을 완료하는데 걸리는 기간 T[i]와 상담을 했을 때 받을 수 있는 금액 P[i]로 이루어짐

- 상담을 적절히 했을 때, 얻을 수 있는 최대 수익을 구하기

 

해결방법

DP 배열을 만들어 퇴사 날까지 얻을 수 있는 수익을 최대로 저장하면서 계산했다. 최대값을 저장해두면서 각 날짜에 상담을 했을 때, 얻을 수 있는 수익을 구하고 저장하면서 문제를 해결했다.

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] T = new int[N+1];		// 상담을 완료하는데 걸리는 기간
        int[] P = new int[N+1];		// 상담 했을 대 받을 수 있는 금액
        int[] DP = new int[N+2];	// 최대 수익을 구하기 위해 저장하는 DP 배열
        int max = Integer.MIN_VALUE;
        int ans = 0;

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

        for(int i = 1; i<N+1; i++){
            // 현재 날짜에서 얻을 수 있는 최대 수익
            max = Math.max(max, DP[i]);
            // 해당 일자의 상담을 진행했을 때, 다음 상담할 수 있는 날짜
            int next = i + T[i];
            // 상담을 기간 안에 끝낼 수 있다면 상담 진행
            if(next < N+2){
            	// 얻을 수 있는 수익 중 최대 수익 저장
                DP[next] = Math.max(DP[next], max + P[i]);
                // 최대 수익인 정답 저장
                ans = Math.max(ans, DP[next]);
            }
        }
        // 정답 출력
        System.out.println(ans);
    }
}