[백준] BOJ_15486 - 퇴사 2

이종찬·2026년 1월 27일

baekjoon

1. 문제 정보

문제 요약: $N$ 일 동안 상담을 진행하여 얻을 수 있는 최대 수익을 구해야 합니다. 각 상담은 완료하는 데 걸리는 기간( $T_i$ )과 받을 수 있는 금액( $P_i$ )이 정해져 있습니다.
핵심 제약:
- 상담을 시작하면 $T_i$ 일 동안 다른 상담을 할 수 없습니다.
- $N+1$ 일째 되는 날 퇴사하므로, 그 이후에 끝나는 상담은 진행할 수 없습니다.
- 입력 $N$ 이 최대 1,500,000입니다. (이 조건이 알고리즘 선택의 핵심입니다.)
난이도: Gold 5
링크: https://www.acmicpc.net/problem/15486

2. 접근 방식

1) 문제의 본질 분석

이 문제의 가장 큰 함정은 $N$ 의 크기입니다. $N=1,500,000$ 이기 때문에 일반적인 DFS(백트래킹)로 접근할 경우 $O(2^N)$ 의 시간 복잡도가 발생하여 100% 시간 초과가 발생합니다.

따라서 우리는 이 문제를 $O(N)$ 선형 시간 안에 해결해야 하며, 이를 위해 DP(Dynamic Programming)를 선택해야 합니다.

2) 알고리즘 설계: DP

DP를 구성하는 방법은 크게 두 가지가 있습니다.

Top-Down (Pull): 현재 시점에서 과거의 최댓값을 가져오는 방식
Bottom-Up (Push): 현재 시점의 결정이 미래의 상태를 갱신하는 방식

이 문제는 현재 날짜( $i$ )에 상담을 하면 $i + T_i$ 일에 수익이 생긴다는 흐름을 가지므로, 현재의 선택이 미래의 값을 갱신하는 'Push' 방식이 직관적입니다.

Key Idea: 오늘( $i$ )까지의 최대 수익(max)을 유지하되, 오늘 시작하는 상담이 끝나는 날( $i + T_i$ )에 수익( $P_i$ )을 더해줍니다.

3) 점화식 및 수식 정의

DP 테이블 정의: $DP[i]$ = $i$ 번째 날까지 얻을 수 있는 최대 수익
전이 방정식 (Transition Equation):
1. 상담을 하지 않는 경우: 어제까지의 최대 수익이 그대로 오늘로 이어집니다.
  
  $DP[i] = \max(DP[i], DP[i-1])$
2. 상담을 하는 경우: 오늘( $i$ ) 상담을 시작하면 $T_i$ 일 후인 $i + T_i$ 일에 수익 $P_i$ 가 들어옵니다. 단, 이때의 기준 수익은 '현재 시점까지의 최대 수익( $DP[i]$ )'이 아니라 '상담 시작 전 확보된 최대 수익( $DP[i]$ 에 이미 반영된 max값)'에 기반합니다.
  
  $DP[i + T_i] = \max(DP[i + T_i], DP[i] + P_i)$

3. 코드 구현

❌ 실패한 코드

날짜 계산과 배열 인덱스 처리에서 미묘한 오류가 있었습니다. 특히 $N$ 일에 딱 맞춰 끝나는 경우와 범위를 벗어나는 경우의 처리가 복잡하게 얽혀 있습니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static int[] T, P, dp;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        T = new int[N + 1];
        P = new int[N + 1];

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

        dp = new int[N + 1]; // 배열 크기가 N+1로 다소 타이트함
        for (int i = 1; i <= N; i++) {
            dp[i] = Math.max(dp[i], dp[i - 1]);

            int t = T[i];
            int p = P[i];
            
            // 조건문 분기가 복잡하고, 인덱스 계산 실수가 발생하기 쉬운 구조
            if (i + t - 1 == N) {
                dp[N] = Math.max(dp[N], dp[i] + p);
            } else if (i + t <= N) {
                dp[i + t] = Math.max(dp[i + t], dp[i] + p);
            }
        }

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

⭕ 정답 코드

DP 테이블의 크기를 넉넉하게 잡고( $N+2$ ), 조건문을 단순화하여 퇴사일( $N+1$ ) 이전에 끝나는 모든 상담을 일관되게 처리했습니다.

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int N;
    static int[] T, P, dp;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        T = new int[N + 1];
        P = new int[N + 1];

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

        // DP 배열을 N+2로 선언하여 OutOfBounds 방지 및 퇴사일(N+1) 계산 용이
        dp = new int[N + 2];
        for (int i = 1; i <= N; i++) {
            // 1. 이전 날짜까지의 최댓값을 현재 날짜로 가져옴 (일을 안 하는 경우 고려)
            dp[i] = Math.max(dp[i], dp[i - 1]);

            int t = T[i];
            int p = P[i];

            // 2. 상담을 진행하는 경우: 퇴사일(N+1)을 넘기지 않는지 체크
            if (i + t <= N + 1) {
                dp[i + t] = Math.max(dp[i + t], dp[i] + p);
            }
        }

        // N일까지 일한 결과는 N+1일에 정산될 수도 있음
        System.out.println(Math.max(dp[N], dp[N + 1]));
    }
}

4. 회고 및 배운 점

💡 실패 원인 분석: '근무일' vs '정산일'

실패한 코드와 정답 코드의 결정적인 차이는 배열의 크기와 퇴사일 기준에 있었습니다.

배열 크기 ( $N+1$ vs $N+2$ ):
- DP를 수행할 때 $i$ 번째 날 $T$ 기간의 일을 하면, 보상은 $i+T$ 일에 들어옵니다.
- $N$ 번째 날에 1일짜리 일을 하면 $N+1$ 일에 끝납니다. 이는 유효한 상담입니다.
- 하지만 dp 배열을 N+1로 잡으면, $N$ 일차 루프에서 dp[i+t] 접근 시 인덱스 에러가 날 가능성을 막기 위해 복잡한 if문이 필요해집니다.
- 해결: dp[N+2]로 넉넉히 선언하면, 퇴사일 이후에 끝나는 일도 계산은 하되(if문으로 필터링), 배열 인덱스 초과 오류를 구조적으로 방지할 수 있습니다.
경계값 처리 (Boundary Condition):
- 문제에서 "퇴사일"은 $N+1$ 일입니다. 즉, 상담이 끝나는 시점이 $N+1$ 일이라면 돈을 받을 수 있습니다.
- 실패 코드는 i + t - 1 == N처럼 종료 시점을 기준으로 복잡하게 생각했지만, 정답 코드는 i + t <= N + 1 (끝나는 날이 퇴사일보다 같거나 빠르면 됨)로 직관적으로 처리했습니다.

🚀 구현 디테일

Max Value Propagation: dp[i] = Math.max(dp[i], dp[i-1]) 구문이 매우 중요합니다. $i$ 일에 상담을 시작하지 않더라도, $i-1$ 일까지 벌어둔 최대 수익은 유지되어야 하기 때문입니다. 이 부분이 누락되면 중간에 수익이 0으로 초기화되는 논리적 오류가 발생합니다.