BOJ15486 퇴사2

https://www.acmicpc.net/problem/15486 (opens new window)

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

입력 설정

날짜는 1일 부터 시작하고 금액을 수령받는 것은 n + 1일 째 되는날이기 때문에 배열의 크기를 n + 2로 설정한다.

int[] t = new int[n + 2];
int[] p = new int[n + 2];
int[] dp = new int[n + 2];

제출 코드

이제 가장 큰 값을 구하기 위해 반복문을 진행한다.

미리 해당 날짜의 금액을 받는 날 dp의 값을 최대값으로 갱신해준다. 이전까지 최대값 + 이번에 더할 돈과 그전에 만든 돈 중 큰 값을 비교하여 갱신한다.

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

    int day = i + t[i];
    if (day <= n + 1) {
        dp[day] = Math.max(dp[day], max + p[i]);
    }
}

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ15486 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        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++) {
            t[i] = scanner.nextInt();
            p[i] = scanner.nextInt();
        }

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

            int day = i + t[i];
            if (day <= n + 1) {
                dp[day] = Math.max(dp[day], max + p[i]);
            }
        }

        System.out.println(max);
    }
}

#BOJ #다이나믹 프로그래밍