[백준/DP] 2839번 설탕 배달 (JAVA)

문제

---

풀이

DP 정복을 위해 이번 주는 DP로 불태운다... 차근차근 하자...

이 문제 풀이는 다음과 같다.

1. n이 5의 배수면 5로 나눈 값이 정답이다.
2. 아니라면, dp()에서 최솟값을 계산한다.
   • 3부터 n까지 탐색하며 dp 배열을 채운다.
   • 각 i에 대해, 3과 5로 채울 수 있는 경우는 다음 세 가지가 있다.
     1) 5의 배수인 경우
     → 최솟값을 보장하기 때문에 바로 continue해서 다음 i로 넘어갈 수 있다.
     2) 3의 배수인 경우
     → 최솟값을 보장하지 않기 때문에 아래의 경우를 함께 고려해야 한다.
     3) 3과 5의 합으로 완성되는 경우
     → 이전에 계산해놓은 dp 배열을 활용해서 계산한다. (i-1, 1), (i-2, 2), ... (i/2, i/2)의 수 조합으로 i를 완성할 수 있는지 확인하는 것이다.
   • 만약 i를 3과 5로 채울 수 없는 경우 -1을 저장한다.

코드

import java.io.*;

public class Main {

    private static final int IMPOSSIBLE = -1;
    private static final int MAXIMUM = 5000;

    private static int n;
    private static int[] dp = new int[MAXIMUM + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        if (n % 5 == 0) dp[n] = n / 5;
        else dp();
        bw.append(Integer.toString(dp[n]));

        br.close();
        bw.close();
    }

    private static void dp() {
        dp[1] = IMPOSSIBLE;
        dp[2] = IMPOSSIBLE;
        for (int i = 3; i <= n; i++) {
            if (i % 5 == 0) {
                dp[i] = i / 5;
                continue;
            }
            int min = (i % 3 == 0 ? i / 3 : Integer.MAX_VALUE);
            for (int j = i - 1; j >= i / 2; j--)
                if (dp[j] != IMPOSSIBLE && dp[i - j] != IMPOSSIBLE)
                    min = Math.min(min, dp[j] + dp[i - j]);
            dp[i] = (min == Integer.MAX_VALUE ? IMPOSSIBLE : min);
        }
    }
}