📌 [코딩테스트] 백준 2839번 설탕 배달 - 자바

안녕하세요! 오늘은 백준 2839번 "설탕 배달" 문제를 자바로 해결하는 방법을 정리해보겠습니다. 이 문제는 그리디 알고리즘을 활용하여 최소한의 봉지 개수로 정확한 무게를 만드는 문제입니다.

---

문제 설명

상근이는 설탕을 배달해야 합니다. 설탕은 3kg 봉지와 5kg 봉지로만 포장되어 있으며, 정확히 N킬로그램을 만들기 위해 필요한 최소한의 봉지 개수를 구하는 문제입니다.

조건

• 봉지는 3kg과 5kg 두 종류만 존재합니다.
• 최대한 적은 개수의 봉지를 사용해야 합니다.
• 정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다.

입력

• 첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

• 상근이가 배달하는 봉지의 최소 개수를 출력합니다.
• 정확하게 N킬로그램을 만들 수 없다면 -1을 출력합니다.

예제 입력 및 출력

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

 

---

풀이 과정

이 문제는 그리디 알고리즘(Greedy Algorithm) 을 사용하여 해결할 수 있습니다. 최소한의 봉지를 사용해야 하므로, 5kg 봉지를 최대한 많이 사용하고, 남은 무게를 3kg 봉지로 채우는 방식이 최적의 방법입니다.

해결 방법

1. 먼저 5kg 봉지를 최대한 많이 사용합니다.
2. 남은 무게가 3kg으로 나누어 떨어지는지 확인합니다.
3. 나누어 떨어지면 봉지 개수를 출력하고, 아니라면 5kg 봉지 하나를 줄이고 다시 검사합니다.
4. 만약 5kg 봉지를 줄였음에도 정확한 무게를 만들 수 없다면 -1을 출력합니다.

---

코드 구현 (Java)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int count = 0;

        while (N >= 0) {
            if (N % 5 == 0) { // 5kg 봉지로 나누어 떨어지는 경우
                count += N / 5;
                System.out.println(count);
                return;
            }
            N -= 3; // 5kg로 안되면 3kg 봉지 하나 사용
            count++;
        }
        System.out.println(-1); // 정확한 무게를 만들 수 없는 경우
    }
}

 

 

---

코드 설명

• 입력 받기: Scanner를 사용하여 N을 입력받습니다.
• 5kg 봉지를 우선 사용: N % 5 == 0 인 경우, 5kg 봉지로 나누어떨어지므로 개수를 출력하고 종료합니다.
• 3kg 봉지를 하나씩 사용: 5kg으로 나누어떨어지지 않는다면, N에서 3kg을 빼고 봉지 개수를 증가시킵니다.
• 반복문 종료 조건: N이 0보다 작아지면 정확한 무게를 만들 수 없는 경우이므로 -1을 출력합니다.

---

시간 복잡도 분석

• 5kg 봉지를 최대한 많이 사용하면서 3kg씩 줄여나가는 방식이므로, 최악의 경우 N이 5000일 때 약 1667번(5000/3) 연산이 필요합니다.
• 이는 O(N)보다 훨씬 적은 연산 횟수이므로, 시간 복잡도는 O(N/3) ≈ O(N) 이라고 볼 수 있습니다.

---

결론

이 문제는 그리디 알고리즘 을 활용하여 최적의 해를 빠르게 구하는 문제입니다. 핵심은 5kg 봉지를 최대한 사용하고, 나머지를 3kg 봉지로 채우는 방식입니다.

이제 더 어려운 문제도 도전해보겠습니다! 🚀

다음 코딩테스트 문제에서 또 만나요! 😊