[백준] 15486. 퇴사 2

문제 링크

[백준] 15486. 퇴사 2

풀이 과정

다이나믹 프로그래밍 문제입니다. 문제의 첫번째 입력 예시로 설명하겠습니다.

0일날의 상담은 총 3일이 걸리기 때문에, 0일의 상담을 하면, 3일부터 다른 상담을 진행할 수 있습니다. 다시말해, 1일과 2일의 상담은 진행하지 못합니다.

0일날 상담을 진행했다 치면, 배열 dp에 3번째 요소 값을 갱신합니다. dp[3]은 3일째 되었을 때 얻을 수 있는 최대 이익을 의미합니다. 여기서 dp[3]이 3일날의 상담은 진행한 것이 아니라는 점을 주의해야 합니다.

1일날의 상담은 총 5일이 걸리며, 위와 같은 방법으로 dp[6]은 20이 됩니다. 1일까지의 데이터만으로 6일자 최대 이익을 갱신했습니다. 여기까지의 두 데이터만으로 봤을 때, 7일이 되는날 얻을 수 있는 최대 이익은 20이 됩니다.

2일날의 상담은 총 1일이 걸립니다. 이 때, 배열 dp의 3번째 요소 dp[3]에는, 0일째 되던날(바로 위 사진의 왼쪽 그림) 미리 구해놨던 값이 존재합니다. 이 두 값은 같게 되고, 위에서 볼 수 있듯이 0일날의 상담을 진행하거나, 2일날의 상담을 진행하거나, 둘 중 하나의 상담을 진행하여 3일째 되었을 때 얻을 수 있는 최대 이익은 같다고 판단할 수 있습니다.

마찬가지 방법으로, 3일날의 상담은 총 1일이 걸리며, 4일까지의 최대 이익을 의미하는 dp[4]에는 3일까지의 최대 이익 dp[3]에 3일의 상담 이익 P[3]을 더한 30이 저장됩니다. (dp[4] = dp[3] + P[3])

4일날의 상담은 총 2일이 걸리며, 6일까지의 최대 이익을 의미하는 dp[6]에는 4일까지의 최대 이익 dp[4]에 4일의 상담 이익 P[4]를 더한 값 45가 저장됩니다. (dp[6] = dp[4] + P[4])

5일날의 상담과 6일날의 상담은 진행하면 퇴사일이 넘어가기 때문에 패스합니다.

인덱스는 0을 시작으로 6까지 설정해뒀으므로, 7일이 되는 날에는 정산을 합니다. 배열 dp에 존재하는 가장 큰 값이 얻을 수 있는 최대 이익이 됩니다.

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

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

• N일이 되는 날까지 포함해야 하므로, 인덱스는 0부터 N까지 순회합니다.
• max 라는 변수를 두고, dp 각 요소와 비교하여 항상 max를 최대값으로 설정합니다.
• dp[i + T[i]] = Math.max(dp[i + T[i]], max + P[i]);
  1. i + T[i] 날짜에 갱신되었던 값(= i - 1 일자까지의 상담들만을 고려하여 설정되었던 최대 이익 값) dp[i + T[i]]
  2. i 날의 상담을 진행했을 때의 이익(max + P[i])
  3. 위 두 값 1, 2를 비교하여 더 큰 값으로 갱신합니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] T = new int[N];
        int[] P = new int[N];
        int[] dp = new int[N + 1];
        int max = 0;

        for (int i = 0; i < N; i++) {
            T[i] = sc.nextInt();
            P[i] = sc.nextInt();
        }

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

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

        System.out.println(max);
    }
}