백준 문제 풀이: [2839] 설탕 배달 (JAVA)

---

문제 링크: https://www.acmicpc.net/problem/2839

문제 설명:

상근이는 N kg의 설탕을 배달해야 합니다. 설탕은 3kg 봉지와 5kg 봉지만 존재하며, 가장 적은 개수의 봉지를 사용해 N kg을 배달해야 합니다. 만약 정확히 N kg을 만들 수 없다면 -1을 출력해야 합니다.

---

문제 해결 코드

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

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 greedyResult = greedyApproach(N);
        int dpResult = dpApproach(N);

        // 결과 출력
        System.out.println("그리디 알고리즘 결과: " + greedyResult);
        System.out.println("동적 계획법 결과: " + dpResult);
    }

    // 1️⃣ **그리디 알고리즘 풀이**
    public static int greedyApproach(int N) {
        for (int i = N / 5; i >= 0; i--) { // 5kg 봉지를 최대한 많이 사용
            int remaining = N - (i * 5);
            if (remaining % 3 == 0) { // 나머지가 3kg 봉지로 나누어 떨어질 때
                return i + (remaining / 3); // 봉지 개수 리턴
            }
        }
        return -1; // 나누어 떨어지지 않는 경우
    }

    // 2️⃣ **동적 계획법(DP) 풀이**
    public static int dpApproach(int N) {
        int[] dp = new int[N + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; // 0kg은 0개의 봉지 필요

        for (int i = 3; i <= N; i++) {
            if (i >= 3 && dp[i - 3] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - 3] + 1); // 3kg 추가한 경우
            }
            if (i >= 5 && dp[i - 5] != Integer.MAX_VALUE) {
                dp[i] = Math.min(dp[i], dp[i - 5] + 1);  // 5kg 추가한 경우
            }
        }

        return (dp[N] == Integer.MAX_VALUE) ? -1 : dp[N];  // 만들 수 없는 경우 -1 반환
    }
}

---

코드 설명

이 문제를 해결하기 위해 두 가지 접근 방식을 사용했습니다: 그리디 알고리즘과 동적 계획법(DP).

• 그리디 알고리즘: 가장 큰 단위(5kg)부터 가능한 한 많이 사용하고, 나머지가 3kg으로 나누어 떨어지면 봉지 개수를 반환합니다.
• 동적 계획법(DP): dp 배열을 활용하여 N kg을 만들기 위한 최소 봉지 개수를 저장합니다. dp[i]는 i kg을 만들기 위한 최소 봉지 개수이며, 3kg 또는 5kg을 추가할 때 최소 개수를 유지합니다.
• 시간 복잡도 분석:
  • 그리디 알고리즘: O(N / 5) = O(N)
  • 동적 계획법: O(N) (배열을 한 번 순회하며 최적 해를 찾음)

---

결과

예제 입력과 예상되는 결과:

입력:
18

출력:
그리디 알고리즘 결과: 4
동적 계획법 결과: 4

두 방법 모두 최소 4개의 봉지를 사용해야 한다는 결과를 반환합니다.

 

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!