[BOJ] 14501 - 퇴사

문제

https://www.acmicpc.net/problem/14501

링크를 확인해보세요.

www.acmicpc.net

문제 정리

시간 제한	메모리 제한	정답 비율
2 초	512 MB	51.4%

요약

• 상담원 백준이는 N + 1일에 퇴사할 예정입니다.
• 1 ~ N 일 차까지 상담 일정이 주어집니다.
  • T_i : i일차부터 상담완료 되는 시간.
  • P_i : i일차의 상담을 완료했을 때 얻을 수 있는 수익.
• 한 번에 하나의 상담만 수락할 수 있으며, 상담이 끝나야 새로운 상담을 수락할 수 있습니다.
  • T_1 = 3일 때 1일차의 상담을 진행하는 경우 4일차부터 새로운 상담을 수락할 수 있습니다.
• N + 1일에는 회사에 없어서 i + T_i > N + 1일 인 경우 i일차에 상담을 수락할 수 없습니다.
• 백준이가 퇴사까지 얻을 수 있는 최대 수익을 구하시오.

입력 조건

• N : 1 ~ 15
• T : 1 ~ 5
• P : 1 ~ 1000

출력

첫 줄에 백준이 얻을 수 있는 최대 이익

문제 풀이

문제를 보고 바로 Knapsack Problem 문제와 아주 유사하다고 느꼈습니다. 따라서 우선 DP로 접근하였습니다.

DP[i]를 i일차에 얻을 수 있는 최대 수익이라고 생각해 보겠습니다.

i일차에 얻을 수 있는 수익은 다음 중 더 큰 값이 됩니다.

• i일차 상담을 수락한 경우 P_i + DP[i + T_i]
• i일차 상담을 거절한 경우 DP[i + 1]

여기서 보면 i일차는 i + T_i의 영향받는 것을 알 수 있습니다. 따라사 Top-Down 방식으로 해결할 수 있습니다.

풀이 코드

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

class Main {

    void solve() throws Exception {
        // 변수 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] data = new int[N][];

        for (int i = 0; i < N; i++) {
            data[i] = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();
        }

        int[] DP = new int[N + 1];

        // DP 탐색
        for (int i = N - 1; i >= 0; i--) {
            if (i + data[i][0] > N) {
                // 이미 퇴사해서 상담을 완료 할 수 없는 겨우.
                DP[i] = DP[i + 1];
            } else {
                DP[i] = Math.max(
                        DP[i + 1], // 상담을 수락하지 않은 경우
                        data[i][1] + DP[i + data[i][0]] // 상담을 수락한 경우
                );
            }
        }

        // 출력
        System.out.println(DP[0]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solve();
    }
}