[백준] 2839번 : 설탕 배달 – JAVA [자바]

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

2839번: 설탕 배달

 

---

• 문제

 

 

---

• 문제 풀이

백준 2839번 설탕 배달은 실버 4 난이도의 수학, DP 그리고 그리디 문제이다. 이 문제에서는 설탕 무게 N이 주어진다. 그리고 설탕 봉지는 3 킬로그램 봉지와 5 킬로그램 봉지만 있다. 이때 최대한 적은 봉지를 사용해서 무게 N을 맞혀야 한다.

 

이 문제는 다이나믹 프로그래밍, 즉 DP 문제이다. DP 문제 중에서도 대표적인 문제 유형이므로 꼭 풀어보고 이해하는 것을 추천한다. 

 

이 문제는 다음과 같은 공식으로 풀 수 있다.

 

dp [i] = Math.min(dp [i - 3], dp [i - 5]) + 1  , 단 i ≥ 8

 

이 문제에서는 최소의 봉지만 쓰기를 원한다. 따라서, i - 3의 무게가 쓰는 봉지의 개수 그리고 i - 5의 무게가 쓰는 봉지의 개수 중에 더 적게 쓰는 개수를 고르고 거기에서 +1을 시켜주면 된다. 하지만 여러 개의 케이스가 있으므로 살펴보겠다.

 

Case 1 : dp [i - 3] != -1 && dp [ i- 5] != -1

무게 i - 3와 i - 5가 쓰는 봉지의 개수와 둘 다 -1이 아니므로 Math.min(dp [i - 3], dp [i - 5]) + 1을 해주면 된다.

 

Case 2 : dp [i - 3] == -1 && dp [i - 5] != -1

이번 경우는 무게 i - 3을 만들 수 없는 경우이다. 이 때는 dp [i - 5] + 1을 해준다.

 

Case 3 : dp [i - 3] != -1 && dp [i - 5] == -1

이번 경우는 무게 i - 5를 만들 수 없는 경우이다. 이 때는 dp [i - 3] + 1을 해준다.

 

Case 4 : dp [i - 3] == -1 && dp [i - 5] == -1

무게 i - 3와 i - 5가 쓰는 봉지의 개수와 둘 다 -1이므로 무게 i를 만들 수 있는 경우는 없다. 이때 dp [i] = -1이 된다.

 

---

• 코드

 

import java.io.*;
import java.util.*;
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[5001];
        for (int i = 8; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[3] = dp[5] = 1;
        dp[4] = dp[7] = -1;
        dp[6] = 2;
        for (int i = 8; i <= n; i++) {
            if (dp[i-3] != -1 && dp[i-5] != -1) {
                dp[i] = Math.min(dp[i-3], dp[i-5]) + 1;
            } else if (dp[i-3] != -1) {
                dp[i] = dp[i-3] +1;
            } else if (dp[i-5] != -1) {
                dp[i] = dp[i-5] +1;
            } else {
                dp[i] = -1;
            }

        }
        System.out.print(dp[n]);
    }
}