[BOJ][Java] 15486. 퇴사 2

문제

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

 

문제 이해

• N일 동안 가능한 상담 일정이 주어진다.
  • 상담의 기간, 수익
• N + 1일째 되는 날 퇴사하기 위해, 퇴사 전(N일 내)에 끝나는 상담들을 선택해 최대 수익을 구한다.
• 하루에 하나의 상담만 할 수 있어서, 상담을 시작하면 해당 상담 기간 동안 다른 상담은 할 수 없다.
• 끝나는 날이 N일을 넘어가면 그 상담은 수행할 수 없다.

 

DP 구현

• dp[i]: i일까지의 최대 이익

1. 전날 이익 저장

    dp[i] = max(dp[i], dp[i-1])

2. i일에 상담을 시작
   • 끝나는 날: end = i + consults[i].t - 1
   • 퇴사 전에 끝나는 상담만 유효: end <= n
   • i - 1일까지의 최대 수익에 이번 상담의 수익을 더해서 최댓값 반영

     dp[end] = max(dp[end], dp[i - 1] + consults[i].p)

• 최종 수익: dp[n]
  
  

코드

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

public class Main {
	static class Consult {
		int t, p;

		public Consult(int t, int p) {
			this.t = t;
			this.p = p;
		}
	}

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

		int n = Integer.parseInt(br.readLine());
		Consult[] consults = new Consult[n + 1];

		for (int i = 1; i <= n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			consults[i] = new Consult(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		} // 입력 끝

		int[] dp = new int[n + 1]; // idx일까지의 최대 수익

		for (int i = 1; i <= n; i++) {
			dp[i] = Math.max(dp[i], dp[i - 1]);

			int end = i + consults[i].t - 1; // 끝나는 날
			if (end <= n)
				dp[end] = Math.max(dp[end], dp[i - 1] + consults[i].p);
		}

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