[백준_2839] 설탕 배달 - JAVA

문제 출처

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

풀이

1. DP / Greedy 알고리즘으로 해결할 수 있는 문제이다.
2. DP를 이용하여 문제를 해결하였다.
3. 각 KG 마다 구성할 수 있는 설탕의 갯수를 구성하여 점화식을 세운다.
   세운 점화식을 기반으로 DP를 구성하면 된다.
   dp5 - 5Kg을 최대한 활용하여 구성할 수 있는 설탕 갯수
   dp3 - 3Kg을 최대한 활용하여 구성할 수 있는 설탕 갯수

코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int[] dp = new int[5001];
        Arrays.fill(dp, -1);

        dp[3] = 1;
        dp[5] = 1;
        int N = Integer.parseInt(stringTokenizer.nextToken());
        for (int i = 6; i <= N; i++) {
            int dp3 = Integer.MAX_VALUE, dp5 = Integer.MAX_VALUE;
            if (dp[i - 5] != -1) {
                dp5 = dp[i - 5] + dp[5];
            }
            if (dp[i - 3] != -1) {
                dp3 = dp[i - 3] + dp[3];
            }
            dp[i] = Math.min(dp3, dp5) != Integer.MAX_VALUE ? Math.min(dp3, dp5) : -1;
        }

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

결과