백준 14501·15486 Java: 퇴사 문제를 같은 O(N) DP로 풀기

백준 14501번 ‘퇴사’와 15486번 ‘퇴사 2’는 날짜별 상담 기간과 수익이 주어질 때, 퇴사일을 넘기지 않으면서 얻을 수 있는 최대 수익을 구한다. 원문에서는 부분집합 탐색 대신 두 문제에 공통으로 쓸 수 있는 DP를 선택했다.

• 백준 14501번 퇴사
• 백준 15486번 퇴사 2

두 문제의 원리는 같다. 다만 ‘퇴사 2’는 입력이 커서 지수 탐색이나 느린 입력 처리 대신 O(N) 전이가 필요하다.

dp를 하루가 시작될 때의 최대 수익으로 정의하기

0-based index에서 dp[day]를 day일이 시작될 때까지 확정할 수 있는 최대 수익으로 정의한다. 각 날짜에는 두 선택이 있다.

1. 상담을 하지 않는다: dp[day + 1]에 현재 수익을 전달한다.
2. 상담을 한다: 끝나는 날 day + duration[day]에 현재 수익과 상담 수익을 더해 전달한다.

dp[day + 1] = max(dp[day + 1], dp[day])

finish = day + duration[day]
finish <= N 이면
dp[finish] = max(dp[finish], dp[day] + profit[day])

상담이 끝나는 날부터 다음 상담을 시작할 수 있으므로 finish == N도 유효하다. 가장 자주 생기는 off-by-one 지점이다.

두 문제에 사용할 수 있는 Java 코드

입력이 날짜 순서대로 오므로 상담 객체나 전체 기간·수익 배열을 따로 저장할 필요가 없다. 현재 줄을 읽을 때 이전 상담들이 만든 dp[day]가 이미 준비되어 있다.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws Exception {
        FastScanner scanner = new FastScanner();
        int dayCount = scanner.nextInt();
        int[] dp = new int[dayCount + 1];

        for (int day = 0; day < dayCount; day++) {
            int duration = scanner.nextInt();
            int profit = scanner.nextInt();

            dp[day + 1] = Math.max(dp[day + 1], dp[day]);

            int finish = day + duration;
            if (finish <= dayCount) {
                dp[finish] = Math.max(dp[finish], dp[day] + profit);
            }
        }

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

    private static final class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int index;
        private int size;

        int nextInt() throws IOException {
            int value = 0;
            int character;

            do {
                character = read();
            } while (character <= ' ');

            while (character > ' ') {
                value = value * 10 + character - '0';
                character = read();
            }
            return value;
        }

        private int read() throws IOException {
            if (index >= size) {
                size = input.read(buffer);
                index = 0;
                if (size == -1) {
                    return -1;
                }
            }
            return buffer[index++];
        }
    }
}

뒤에서 보는 DP와 앞에서 보내는 DP

원문 코드는 뒤에서 앞으로 순회하며 dp[i]를 i일부터 얻을 수 있는 최대 수익으로 정의했다. 그 방식도 맞다.

이번 코드는 앞에서 뒤로 수익을 보낸다. 입력을 읽는 즉시 처리할 수 있고, ‘오늘을 건너뛴 값’과 ‘상담이 끝난 날로 보낼 값’을 각각 한 줄로 확인할 수 있다는 장점이 있다. 어느 방향이 더 우월한 것이 아니라 dp[index]의 뜻을 먼저 적고 끝까지 유지하는 것이 중요하다.

원문에서는 Consult 클래스로 기간과 수익을 묶어 가독성을 높이려 했다. 작은 14501번에는 자연스러운 선택이다. 그러나 큰 입력까지 같은 코드로 다룰 때는 객체를 날짜 수만큼 만들지 않고 이름 있는 지역 변수 두 개로 의미를 보존하는 편이 메모리 부담이 작다.

두 행의 선택 상태를 나누는 백준 9465 스티커, 구간의 선택 결과를 합치는 백준 11066 파일 합치기와 비교하면 DP 상태를 정하는 방식의 차이가 보인다.

검증 범위

Java source를 수동 검토했다. 하루짜리 일정, 모든 상담이 퇴사일을 넘는 경우, 정확히 마지막 날에 끝나는 상담과 겹치는 상담을 포함한 작은 무작위 일정을 완전 탐색 결과와 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.