[BOJ] 2839 설탕 배달 (Java, Greedy)

문 제  정보

문제 : 백준 2839번 설탕 배달

난이도 : 실버 4

알고리즘 : Greedy

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

 

문제 요약

주어진 N kg의 설탕은 3kg과 5kg의 설탕 봉지로 정확하게 배달해야 한다. 이때 최소의 봉지 개수값을 구하는 문제

 

 

접근 방법

처음에는 동적 프로그래밍(DP)을 생각했다. 시간 복잡도가 O(N)이라 입력 가능한 N의 최대값 5000에도 무사히 들어오는 수치였다. 그렇지만 과연 방법이 DP밖에 없을까 고민해보다가 브루트 포스와 그리디로는 해결이 안될까?라고 생각이 들었고 N은 최대 5000이라는 작은 값이므로 브루트 포스보다는 그리디가 더 직관적이고 짧을 것 같아서 그리디로 접근해보았다.

 

 

알고리즘

최대한 적은 봉지 수를 이용하는 것이 핵심이므로

1. 5kg 봉지를 최대한 이용하기

2. 5kg 봉지를 최대한 이용하고 남은 봉지가 3으로 나누어떨어지면 종료

 

 

코드

import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int count = 0;

        while(N >= 0) { // 입력받은 N이 0보다 크거나 같은 동안에 계속 수행
            if(N % 5 == 0) { 
                count += N / 5; // N이 5로 나누어떨어진다면 N을 5로 나눈 몫만큼 count변수에 더함.
                System.out.println(count);
                return;
            }
            N -= 3; // N이 5로 나누어떨어지지 않는다면 3을 빼고
            count++; // 3kg 봉지에 한번 담은 것으로 간주하여 count += 1
        }

        System.out.println(-1); // 어떻게해도 만들기 불가능하다면 -1을 출력


    }
}

 

 

시간 복잡도

O(N) -> 실질적으로는 O(N/3)이지만 빅오 표기법상 O(N)이다. N이 5로 나누어떨어지는 경우에는 단 한번으로 가능하지만 그렇지않다면 매번 3을 빼야한다. 

 

 

배운 점

이 문제는 다이나믹 프로그래밍 등 해결할 수 있는 방법이 더 많았지만, 그 중에서도 그리디로 해결하는 것이 짧고 직관적일 것 같았다. 또한 최소값을 구할때 큰 단위부터 사용하다보면 정답을 더 쉽게 구할 수 있다 라는 것을 알게 되었다.