[JAVA]백준 알고리즘 2839번 : 설탕 배달

https://www.acmicpc.net/problem/2839

2839번: 설탕 배달

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

 

풀이

봉지를 최소 몇 개를 가져가야 하는지 구하는 문제이다.

 

이 문제는 해결하는 방법이 여러 가지 있을 것이다.

필자는 N이 5의 배수인 경우, 3의 배수인 경우, 둘 다 아닌 경우로 나누어 해결하였다.

 

먼저 알아두어야 할 것은, 5kg짜리 봉지를 많이 사용하면 봉지의 개수가 줄어든다는 것이다.

 

1. N이 5의 배수인 경우

이 경우는 가장 간단하게 해결할 수 있다.

봉지의 개수는 N / 5개이다.

 

2. N이 3의 배수인 경우

이 경우에도 봉지의 개수는 N / 3개라고 생각할 수 있지만, 그렇지 않다.

 

이 경우는 또 두 가지로 나누어 생각해야 한다.

위 그림은 30kg을 3kg짜리 10개, 5kg짜리 6개로 나타낸 것이다.

이처럼 15보다 큰 3의 배수는 15kg를 5kg짜리 3개를 사용하여 봉지의 개수를 줄일 수 있기 때문에, N이 15보다 큰 3의 배수인지, 15보다 작은 3의 배수인지를 생각해야 한다.

 

2-1. N이 15보다 크거나 같은 3의 배수인 경우

이 경우, 봉지의 개수는 N / 15 * 3 + N % 15 / 3개이다.

N / 15 * 3 : N을 15로 나눈 몫에 3을 곱하면, 5kg짜리 봉지의 개수가 된다. 15kg를 5kg * 3으로 만들 수 있기 때문에, 15kg 당 봉지가 3개 필요하기 때문.

N % 15 / 3 : N을 15로 나눈 나머지를 3으로 나누면, 3kg짜리 봉지의 개수가 된다. 15kg가 넘어가는 3의 배수는 5kg짜리로 해결했기 때문에, 3kg짜리 봉지로는 15kg보다 작은 무게만 만들면 된다.

 

2-2. N이 15보다 작은 3의 배수인 경우

이 경우의 봉지의 개수는 N / 3이다.

 

3-1. N이 5의 배수 또는 3의 배수가 아닌 경우

필자는 이 경우를 해결하기 위해 식을 세워보았다.

 

당연한 것이긴 하지만, Nkg을 아래 식으로 나타낼 수 있다.(A : 3kg짜리 봉지의 개수, B : 5kg짜리 봉지의 개수)

A와 B 둘 중 하나를 0으로 만든다면, N은 3의 배수 또는 5의 배수가 될 것이다.

따라서 필자는 둘 중 하나가 0이 될 때까지 8을 빼는 방법을 사용하였다.(봉지의 개수는 8을 뺄 때마다 2개를 추가하면 된다. 3kg + 5kg)

 

N이 3의 배수 또는 5의 배수가 되었다면, 위의 1, 2번 방법을 사용하여 해결할 수 있다.

 

---

🔔 자세한 코드 설명은 더보기 란에 작성하였습니다.

1. N을 입력받고, 봉지의 개수를 저장할 변수를 선언한다.(count : 봉지의 개수)

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

 

2. 3의 배수와 5의 배수가 아닌 경우, N에서 8을 빼고 count는 2를 더한다.(봉지의 개수가 2개씩 늘어나기 때문)

이 과정에서 음수가 된다면, 3kg와 5kg로 표현할 수 없는 무게이기 때문에 -1을 출력한다.

while(N % 3 != 0 && N % 5 != 0) {
    if(N < 0) {
        System.out.println(-1);
        return;
    }
    N -= 8;
    count += 2;
}

 

3. count 변수에 bag() 함수의 리턴값을 더하고, 출력한다.(bag() 함수 : 위 설명의 1, 2번 과정을 수행하는 함수)

count += bag(N);
System.out.println(count);

 

* bag() 함수

1. 5의 배수일 경우 N / 5를 return 한다.(봉지의 개수가 N / 5이기 때문)

2-1. 15보다 크거나 같은 3의 배수일 경우, N / 15 * 3 + N % 15 / 3을 return 한다.(위에서 설명한 식이다.)

2-2. 15보다 작은 3의 배수일 경우, N / 3을 return 한다.

3. 그 외의 경우, -1을 return 한다.(하지만 이 함수를 수행하기 전에, N을 3의 배수 또는 5의 배수로 만들기 때문에, 그 외의 경우는 없다.)

public static int bag(int N) {
    if(N % 5 == 0) return N / 5;
    else if(N % 3 == 0) {
        if(N >= 15) return N / 15 * 3 + N % 15 / 3;
        else return N / 3;
    }
    return -1;
}

---

코드

BufferedReader 클래스를 이용한 코드

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 count = 0;

        while(N % 3 != 0 && N % 5 != 0) {
            if(N < 0) {
                System.out.println(-1);
                return;
            }
            N -= 8;
            count += 2;
        }
        count += bag(N);
        System.out.println(count);
    }
    public static int bag(int N) {
        if(N % 5 == 0) return N / 5;
        else if(N % 3 == 0) {
            if(N >= 15) return N / 15 * 3 + N % 15 / 3;
            else return N / 3;
        }
        return -1;
    }
}

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!