[Java][백준][골드 5] 퇴사 2 - 15486

1. 문제 정보

• 문제명: 퇴사 2
• 문제 번호: 15486
• 플랫폼: 백준
• 문제 링크: https://www.acmicpc.net/problem/15486
• 알고리즘 유형: DP
• 핵심: 매일 일을 할지 말지 선택하면서 최대 이익을 누적하는 스케줄링 DP

 

2. 문제 요약

N일 동안 상담 일정이 주어진다.
각 날짜 i에는 상담 기간 T[i]와 보상 P[i]가 있고, 상담을 시작하면 T[i]일을 연속으로 사용한다.

퇴사일(N+1)을 넘기면 해당 상담은 할 수 없다.
목표는 퇴사 전까지 얻을 수 있는 최대 수익을 구하는 것이다.

 

3. 내 풀이 아이디어

이 문제는 날짜별로 선택이 갈린다.

• 오늘 상담을 안 하는 경우: 다음 날로 이익을 그대로 넘김
• 오늘 상담을 하는 경우: 상담 종료일의 이익을 갱신

그래서 dp[d] = d일 시점까지 얻을 수 있는 최대 이익으로 두고 진행했다.

핵심 전이는 두 가지다.

• dp[i+1] = max(dp[i+1], dp[i]) (오늘 상담 안 함)
• next = i + T[i]가 가능하면
  dp[next] = max(dp[next], dp[i] + P[i]) (오늘 상담 함)

즉, 네가 적어둔 것처럼 "그 날 일을 할지 안 할지"가 핵심이다.

 

4. 풀이 방법

1. arr[i][0] = T[i], arr[i][1] = P[i]로 입력 저장
2. dp 배열을 n+2 크기로 준비
3. i = 0..n 순회하면서

• 일을 안 하는 전이 먼저 수행
• 일을 하는 전이(next <= n+1) 수행

4. 최종 답 dp[n+1] 출력

• 시간복잡도: O(N)
• 공간복잡도: O(N)

 

5. 내 코드

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

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

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

    for (int i = 1; i <= n; i++) {
        st = new StringTokenizer(br.readLine());
        arr[i][0] = Integer.parseInt(st.nextToken());
        arr[i][1] = Integer.parseInt(st.nextToken());
    }

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

        int next = i + arr[i][0];
        if (next <= n + 1) {
            dp[next] = Math.max(dp[next], dp[i] + arr[i][1]);
        }
    }

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

 

6. 코드 해설

• dp[i+1] 갱신:
  • 해당 날짜에 상담을 건너뛰는 선택
• next 계산 후 dp[next] 갱신:
  • 상담을 선택했을 때 종료 시점 이익 반영
• next <= n+1 체크:
  • 퇴사일을 넘는 상담 제외
• dp[n+1]:
  • 퇴사 시점의 최대 이익

이 구조 덕분에 모든 날짜를 한 번만 보면서 최적해를 구할 수 있다.

 

7. 회고

처음엔 경우를 나눠 생각해야 해서 복잡해 보였지만,
안 한다 / 한다 두 전이로 정리하니 DP가 깔끔하게 풀렸다.

특히 스케줄링 DP에서는 "현재 이익을 다음 시점으로 전달하는 전이"가 핵심이라는 걸 다시 확인한 문제였다.