[BOJ/DP] 백준 14501 - 퇴사 / 15486 - 퇴사 2 (Java)

14501 - 퇴사

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

문제

N + 1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담
각각의 상담은 완료하는데 걸리는 기간 $T_i$, 상담을 했을 때 받을 수 있는 금액 $P_i$
ex. N = 7
1일에 잡혀있는 상담: 총 3일, 받을 수 있는 금액: 10/ 5일에 잡혀있는 상담: 총 2일, 받을 수 있는 금액: 15
-> 상담을 하는데 필요한 기간은 1보다 클 수 있기 때문에, 모든 상담 X
1일에 상담 -> 2, 3일에는 상담 X/ 2일에 상담 -> 3, 4, 5, 6일에 상담 X
/ N + 1일에는 회사에 없기 때문에 6, 7일에 상담 X
=> 퇴사 전에 할 수 있는 상담의 최대 이익: 1일, 4일, 5일, 이익: 10 + 20 + 15 = 45

=> 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익?

입력
첫째 줄: N (1 <= N <= 15)
둘째 줄 ~ N개의 줄: $T_i$, $P_i$가 1일부터 N일까지 순서대로 주어짐(공백)
(1 <= $T_i$ <= 5, 1 <= $P_i$ <= 1,000)
출력: 백준이가 얻을 수 있는 최대 이익

---

풀이

• `T[i]`: i일에 걸리는 상담 기간
• `P[i]`: i일에 받을 수 있는 수익
• `dp[i]`: i일부터 시작해서 얻을 수 있는 최대 이익

 

• 미래에 어떤 상담을 할지 알아야 현재 결정 할 수 있음
• `i + T[i] <= N + 1`: 퇴사 전에 상담이 끝나는 경우만 선택 가능
  • 상담 X = 내일로 넘김: `dp[i + 1]`
  • 상담 O = 수익 받음 + 상담이 끝난 후부터 벌 수 있는 최대 수익: `P[i] + dp[i + T[i]]`

for (int i = N; i >= 1; i--) {
    if (i + T[i] <= N + 1) {
        dp[i] = Math.max(dp[i + 1], P[i] + dp[i + T[i]]);
    } else dp[i] = dp[i + 1];
}

---

코드

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

// 퇴사
public class boj_14501 {
    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];

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

        for (int i = N; i >= 1; i--) {
            if (i + T[i] <= N + 1) {
                dp[i] = Math.max(dp[i + 1], P[i] + dp[i + T[i]]);
            } else dp[i] = dp[i + 1];
        }

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

 

---

15486 - 퇴사 2

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

문제

N + 1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담
각각의 상담은 완료하는데 걸리는 기간 $T_i$, 상담을 했을 때 받을 수 있는 금액 $P_i$
ex. N = 7
1일에 잡혀있는 상담: 총 3일, 받을 수 있는 금액: 10/ 5일에 잡혀있는 상담: 총 2일, 받을 수 있는 금액: 15
-> 상담을 하는데 필요한 기간은 1보다 클 수 있기 때문에, 모든 상담 X
1일에 상담 -> 2, 3일에는 상담 X/ 2일에 상담 -> 3, 4, 5, 6일에 상담 X
/ N + 1일에는 회사에 없기 때문에 6, 7일에 상담 X
=> 퇴사 전에 할 수 있는 상담의 최대 이익: 1일, 4일, 5일, 이익: 10 + 20 + 15 = 45

=> 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익?

입력
첫째 줄: N (1 <= N <= 1,500,000)
둘째 줄 ~ N개의 줄: $T_i$, $P_i$가 1일부터 N일까지 순서대로 주어짐(공백)
(1 <= $T_i$ <= 50, 1 <= $P_i$ <= 1,000)
출력
: 백준이가 얻을 수 있는 최대 이익

---

풀이

• `T[i]`: i일에 걸리는 상담 기간
• `P[i]`: i일에 받을 수 있는 수익
• `dp[i]`: i일까지 벌 수 있는 최대 수익

 

• (i일에 상담 X) `dp[i + 1] = max(dp[i + 1], dp[i])`: 그 다음 날도 최소 현재 수익
• (i일에 상담 O) `i + T[i] <= N + 1`: 퇴사 전에 상담이 끝나는 경우만 선택 가능
  • 상담이 끝나는 날: `dp[i + T[i]]`

for (int i = 1; i <= N; i++) {
    dp[i + 1] = Math.max(dp[i + 1], dp[i]);

    if (i + T[i] <= N + 1) {
        dp[i + T[i]] = Math.max(dp[i + T[i]], dp[i] + P[i]);
    }
}

---

코드

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

// 퇴사 2
public class boj_15486 {
    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];
        long[] dp = new long[N + 2];

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

        for (int i = 1; i <= N; i++) {
            dp[i + 1] = Math.max(dp[i + 1], dp[i]);

            if (i + T[i] <= N + 1) {
                dp[i + T[i]] = Math.max(dp[i + T[i]], dp[i] + P[i]);
            }
        }

        long max = 0;
        for (int i = 1; i <= N + 1; i++) max = Math.max(max, dp[i]);

        System.out.println(max);
    }
}