백준 2839 Java - 설탕 배달

제목 : 설탕 배달

---

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다.

상근이는 지금 사탕가게에 설탕을 정확하게 N 킬로그램을 배달해야 한다.

설탕공장에서 만드는 설탕은 봉지에 담겨져 있다.

봉지는 3 킬로그램 봉지와 5 킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다.

예를 들어, 18 킬로그램 설탕을 배달해야 할 때, 3 킬로그램 봉지 6 개를 가져가도 되지만,

5 킬로그램 3 개 와 3 킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N 킬로그램 배달해야 할 때,

봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N 이 주어진다. (3 <= N <= 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다.

만약, 정확하게 N 킬로그램을 만들 수 없다면, -1 을 출력한다.

예제 입력	예제 출력
18	4
4	-1
6	2
9	3
11	3

---

이 문제는 실 생활에서의 "잔돈 거슬러주기" 문제보다는 조금 더 생각해야 할 문제이다.

실제로 이전 단계의 문제에서는 어떠한 값이던 매칭되는 값이 존재하여

매칭을 못하는 경우는 존재하지 않았다.

예를 들어, 950 원을 거슬러 주어야 한다고 하면,

500원 1개, 100원 4개, 50원 1개 거슬러 주면 될 것이다.

하지만, 이 문제는 3KG, 5KG 으로 설탕을 배달 해 주고 있다.

이 때 발생하는 문제는 2 가지 이다.

1. 정확히 배달 해 주지 못할 무게가 존재한다. EX - 4 KG
2. 매칭 할 수 있는 "모든 경우의 수" 중에서, 가장 적은 봉지를 사용하는 경우를 추출해야 한다는 것.

그런데, 실제로 이 문제가 실 생활 문제라고 생각 해 보자.

내가 만약에 설탕가게 사장인데, 봉지 자체의 값이 비싸 이를 절약하여 최소화 하고자 한다면,

이전에 설탕을 배달했을 때의 최소값을 기억하여 조합 할 것이라고 생각이 든다.

물론, 우리는 컴퓨터를 이용하기 때문에, 최소값을 구할 수 있다.

---

풀이 방식에 대한 견해

1 번째 풀이 방식 (Brute Force)

우리는 컴퓨터를 이용하여 굉장히 빠르게 계산하기 때문에,

배달해야 하는 설탕 봉지의 최소값을 3KG, 5KG 의 기준 중 하나로 구할 수 있다.

원하는 것 하나로 구하면 된다.

예를 들어, 단순히 내가 3KG 을 기준으로 세웠다면, (21 키로의 설탕을 배달한다 가정)

• 3KG x 0개 일 때, 5KG 으로 정확히 나누어지는지, 그렇다면 몇 개가 필요한지 저장
• 3KG x 1개 일 때, 5KG 으로 정확히 나누어지는지, 그렇다면 몇 개가 필요한지 저장
• ...
• 3KG x 7개 일 때, 5KG 으로 정확히 나누어지는지, 그렇다면 몇 개가 필요한지 저장

이러한 과정으로 풀면 될 것이다.

결과적으로, 답은 3KG x 2개, 5KG x 3 으로, 최소 설탕 봉지는 5 개가 될 것이다.

Answer 1 - Brute Force 방식

import java.util.*;
import java.io.*;

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 min = Integer.MAX_VALUE;

        // 3 키로짜리 설탕 봉지 0개에서 시작하여, 
        for(int KG3 = 0; KG3 * 3 <= N; KG3++) {
            // 3KG 짜리 설탕 봉지를 빼고 남은 설탕의 무게.(KG)
            int remain = N - (KG3 * 3);

            // 남은 양이 정확히 5로 떨어진다면,
            if(remain % 5 == 0) {
                // 설탕 5KG 짜리가 몇 개 나오는지 계산.
                int KG5 = remain / 5;

                // 만약 현재 3키로, 5키로 설탕 봉지의 합이 "현재까지의" 최소 봉지보다 적다면, 교체한다.
                min = (KG3 + KG5) < min ? (KG3 + KG5) : min;
            }
        }

        // 만약, 한 번도 나누어 떨어진 적이 없다면, 해당 무게는 배송이 불가능하다.
        if(min == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(min);
        }
    }
}

---

2 번째 풀이 방식 (Dynamic Programming - DP)

사실, 이 방식은 요구 설탕의 최대 크기가 100,000 정도 되며,

배달해야 할 설탕의 개수 또한 10,000 ~ 100,000 정도 될 때 굉장히 유용하게 절약 할 수 있다.

그래서 위의 가정을 어떻게 DP 로 풀어내는가?

결국에 "이전의 값을 저장" 하며, "계산을 최소화" 해 주기 위해서는,

최소값을 저장 해 두는 1 차원 배열이 필요하다.

0 부터 시작해서, 설탕을 전달해야 할 최대 KG 까지 배열 길이를 생성한다. (Length == 5001)

그리고, 0 부터 시작해서, 5001 인덱스를 KG 처럼 생각해서, 차례로 계산한다.

이 방식은 첫 번째 방식보다는 당연히 느리다. 바로 계산하기 때문이다.

하지만, 동일한 입력이 100,000 수준이라면, 기억해 두고 계산하는 것이 중요 할 것이다.

그렇다면, 각 인덱스(KG) 에서 처리될 과정을 생각 해 보자.

0 ~ 10 까지는 직접 작성해 두자.

Answer 2 - DP 방식

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 배달해야 할 총 설탕의 KG
        int N = Integer.parseInt(br.readLine());

        // DP 를 위한 1 차원 배열 - 최대 입력값까지 생성.
        int[] dp = new int[5001];

        // 10 KG 까지 최소값을 저장.
        dp[0] = 0;
        dp[1] = -1;
        dp[2] = -1;
        dp[3] = 1;
        dp[4] = -1;
        dp[5] = 1;
        dp[6] = 2;
        dp[7] = -1;
        dp[8] = 2;
        dp[9] = 3;
        dp[10] = 2;

        // 미리 KG 에 따른 최소값을 저장해 두기 위한 반복문 
        for(int i = 11; i <= 5000; i++) {
            dp[i] = -1;

            // 현재 인덱스가 현재 KG 을 의미한다.
            int currKG = i;

            // 5KG 몫 저장
            int KG5 = currKG / 5;

            // 음수가 아닐 때 까지 진행. - 최대 5KG 봉지 수에서 하나씩 줄여가며 체크
            while (currKG >= 0) {
                // 5KG 봉지를 빼고 남은 설탕 무게.
                int remain = i - (KG5 * 5);

                // 현재 남은 설탕에서 3으로 나누어진다면,
                if(remain % 3 == 0) {
                    // 현재 5KG 설탕 봉지 + 3KG 설탕 봉지가 최소 값이다.
                    dp[i] = KG5 + (remain / 3);
                    break;
                }

                // 딱 나누어지지 않기 때문에, 5KG 봉지를 하나 뺀다.
                KG5--;
            }
        }

        // 최소값까지 이미 계산해 놓은 상황에서, 주어진 "N" 키로를 바로 출력한다.
        System.out.println(dp[N]);
    }
}

위의 방식은 DP 방식의 극히 일부일 뿐이다.

이전의 계산 결과를 토대로,

현재 입력된 값에 대한 결과를 최대한 빠르게 계산하는 것이 DP 의 종류 중 하나이다.

---

논외

1 번째 방식과 2 번째 방식 모두 계산 시간, 사용 메모리가 거의 동일하다.

분명히 DP 방식이 더 많은 시간과 메모리를 할애해야 하지 않나? 생각이 든다.

결과는, 루프가 그리 크지 않기 때문에 실행 시간과 메모리에서의 이점이 거의 없다고 한다.

위의 의문은 GPT 를 통해 해결했습니다.