15486 : 퇴사 2 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공 (50분 8초)

아이디어

이 문제는 퇴사 전까지 얻을 수 있는 최대 상담 수익을 구하는 문제다.
완탐으로 "날짜별로 가능한 모든 경우를 탐색"하려고 하면,
N의 크기가 최대 150만까지 주어지므로 시간 복잡도 때문에 절대 불가능하다.

그래서 난 동적 계획법(DP) 을 썼다.
순서는 이러하다.

1. 상담을 "한다/안 한다"로 나누기

각 날짜 i에서 선택지는 두 가지다.

• dp[i][0] : i번째 상담을 하지 않는 경우의 최대 수익
• dp[i][1] : i번째 상담을 하는 경우의 최대 수익

이렇게 상태를 나누면, 매일 상담을 할지 말지 결정하면서 최적해를 구할 수 있다.

2. 뒤에서부터 거꾸로 계산

퇴사일까지 남은 시간이 한정되어 있으므로,
앞에서부터 풀어나가면 "앞에서 정한 선택이 뒤에 영향을 준다"는 점이 까다롭다.
따라서 뒤에서부터 거꾸로(i=N → 1) 계산하는 방식이 훨씬 자연스럽다.

3. 점화식 세우기

• 상담을 하지 않는 경우

  • 단순히 다음 날의 최대값을 가져오면 된다.
  • dp[i][0] = max(dp[i+1][0], dp[i+1][1])

• 상담을 하는 경우

  • 현재 상담을 잡았을 때, 끝나는 날 이후로 건너뛴 지점의 최대값을 더해야 한다.

  • 만약 i번째 상담이 기간 내에 끝나면:

    • dp[i][1] = max(dp[i+T[i]][0], dp[i+T[i]][1]) + P[i]

  • 만약 기간을 넘어가면 상담을 못 잡으므로, 그냥 다음 날의 최댓값을 가져온다.

4. 최종 답

1일차부터 시작했을 때 얻을 수 있는 최댓값은
max(dp[1][0], dp[1][1])이 된다.

정답 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int [] T = new int[N+2];
        int [] P = new int[N+2];
        int [][] dp = new int[N+2][2];
        for(int i=1; i<=N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int Ti = Integer.parseInt(st.nextToken());
            int Pi = Integer.parseInt(st.nextToken());
            T[i] = Ti;
            P[i] = Pi;
        }
        dp[N][0] = 0;
        dp[N][1] = T[N]!=1?0:P[N];
        for(int i=N-1; i>=1; i--){
            dp[i][0] = Math.max(dp[i+1][0], dp[i+1][1]);
            if(i+T[i]<=N+1){//상담가능
                dp[i][1]= Math.max(dp[i+T[i]][1], dp[i+T[i]][0])+P[i];
            }
            else{
                dp[i][1]= Math.max(dp[i+1][1], dp[i+1][0]);
            }
        }
        System.out.print(Math.max(dp[1][0], dp[1][1]));
    }
}