문제

BOJ 15486: 퇴사 2 https://www.acmicpc.net/problem/15486

풀이

조건

• 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다.
• 상담이 끝나는 날이 퇴사 이후라면 그 상담은 할 수 없다.
• 최대 수익을 구한다.

풀이 순서

• i 날에 끝나는 상담은 i + 1일에 돈을 받는다.
• DP를 사용해 i 날 까지 받을 수 있는 금액을 기록한다.
• i 일 까지의 수익 중 최대값을 기록해 놓는다.
• i 일에 한 상담이 끝나는 날짜를 기록해둔다.(day)
• day가 퇴사 전이라면 해당 날짜까지 받을 수 있는 금액을 DP배열의 해당 위치에 저장한다.

코드

Java

import java.io.*;

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[] time = new int[N + 2];
        int[] pay = new int[N + 2];
        for (int i = 1; i <= N; i++) {
            String[] input = br.readLine().split(" ");

            time[i] = Integer.parseInt(input[0]);
            pay[i] = Integer.parseInt(input[1]);
        }

        // i + 1일에 돈 받음
        int[] dp = new int[N + 2];
        int max = 0; // i 일 까지의 최고 수익
        for (int i = 1; i <= N + 1; i++) {
            // i일 까지의 수익(dp[i])이 최대일 때 max값 갱신
            if (max < dp[i]) {
                max = dp[i];
            }
            // i 일에 상담하면 끝나는 날짜
            int day = i + time[i];
            // 퇴사 전까지 상담을 끝낼 수 있으면
            if (day <= N + 1) {
                // 상담 끝나는 날짜에 
                // '현재 날짜까지의 최대 금액 + 현재 상담 금액' 과
                // '현재 날짜에 기록된 금액' 
                // 중 더 큰 금액 입력
                dp[day] = Math.max(dp[day], max + pay[i]);
            }
        }

        System.out.println(max);
    }

}

정리

• Bottom-Up 방식으로 생각은 했지만 구현하는 데 시간이 오래걸렸다.