백준 2839 - 설탕 배달 (Java)

 

문제 개요

 

백준 - 설탕 배달

 

풀이

그리디 알고리즘을 써야 하는 문제로 이걸 풀려면 상근이가 N 킬로그램의 설탕을 담기 위해 여러 개의 경우의 수가 있을 수 있을 때 그 중 봉지의 수가 가장 적은 경우를 찾아야 한다.

 

즉, 대전제는 5킬로그램 봉지의 수가 가장 많아지는 그 때, 전체 봉지의 수를 출력하면 된다는 것이다.

 

내가 생각한 로직의 처리 순서는 다음과 같다.

 

1. N을 5로 나누어 나누어 떨어지면 나눈 몫을 출력
2. 5로 나누어 떨어지지 않는다면, 나머지를 3으로 나눈 뒤 나누어 떨어진다면 각각의 몫을 더한 값을 출력
   • 5로 나눈 몫 + 3으로 나눈 몫을 출력하면 됨.
3. 위의 방법으로 나누어 떨어지지 않는다면 5의 수를 하나씩 줄여가며 나눈 후 3으로 나누었을 때 나누어 떨어지는지 체크
   • 5의 갯수를 줄였을 때 5의 개수 + 나머지를 3으로 나눴을 때 몫을 출력하면 됨.

 

코드

import java.io.*;

public class Main {

    public static void main(String[] arg) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int input = Integer.parseInt(br.readLine());
        int max = (int) input / 5;
        int answer = -1;

        for (int i=max ; i>=0 ; i--) {
            int nmg = input - (5*i);
            if (nmg == 0) {
                answer = i;
                break;
            }
            if (nmg%3 == 0) {
                answer = (int) nmg/3 + i;
                break;
            }
        }

        System.out.println(answer);
        
        return;
    }
}

 

입출력 방법에 대한 것들은 제쳐두고 로직만 살펴보자.

 

1. input 변수에 입력받은 N(=설탕 무게)을 저장
2. 5킬로그램 봉지가 가장 많을 때의 5킬로그램 봉지의 수를 변수 max에 저장
3. 루프 변수 i를 5킬로그램 봉지의 수라고 가정할 것이므로 max에서 0으로 1씩 감소하는 루프를 작성
4. 루프 내부에서는 input을 5로 나눈 나머지를 nmg에 저장하고, 이 nmg가 0이라면 answer에 i를 대입하고 루프를 종료한다.
5. nmg가 0이 아닌 경우, 3으로 나누어 0이 되면 answer에 nmg를 3으로 나눈 몫 + i 를 대입하고 루프를 종료한다.
6. 만약 입력받은 변수 input이 5와 3으로 나눌 수 없는 수였다면 answer의 초기 값인 -1이 출력될 것이다.
   • 문제에서 나눌 수 없는 경우에는 -1을 출력하라고 강제했기 때문이다.

 

 

제출 결과