[백준] 11985. 오렌지 출하

문제 링크

[백준] 11985. 오렌지 출하

풀이 과정

다이나믹 프로그래밍 문제입니다.

long[] dp = new long[N + 1];

dp[i]는 i번째 오렌지까지 포장했을 때의 최소 금액을 의미합니다.

for (int i = 1; i <= N; i++) {
    dp[i] = Long.MAX_VALUE;
    long max = size[i], min = size[i];

    for (int j = i; j >= Integer.max(1, i - M + 1); j--) {
        max = Math.max(max, size[j]);
        min = Math.min(min, size[j]);
        dp[i] = Math.min(dp[i], dp[j - 1] + K + (i - j + 1) * (max - min));
    }
}

i를 1을 시작으로 dp[i]를 갱신시켜 나갑니다.

1. 먼저 dp[i]를 최대값으로 설정합니다.
2. 한 상자에 오렌지를 최대 M개까지 담을 수 있으므로, j를 i - M +1 까지 감소시키며, i번 오렌지까지의 최소 포장 비용을 갱신합니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int[] size = new int[N + 1];
        long[] dp = new long[N + 1];

        for (int i = 1; i <= N; i++) size[i] = sc.nextInt();

        for (int i = 1; i <= N; i++) {
            dp[i] = Long.MAX_VALUE;
            long max = size[i], min = size[i];

            for (int j = i; j >= Integer.max(1, i - M + 1); j--) {
                max = Math.max(max, size[j]);
                min = Math.min(min, size[j]);
                dp[i] = Math.min(dp[i], dp[j - 1] + K + (i - j + 1) * (max - min));
            }
        }

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