설탕배달

문제

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

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

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

입력

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

출력

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

---

문제를 이해해보자

1. 상근이는 3Kg봉지와 5kg봉지만 가지고 있다.
2. 배달해야할 설탕 N kg이 주어졌을 때 3kg과 5kg봉지만 가지고 정확하게 무게를 맞춰야한다.
3. 만약 무게를 맞출 수 없으면 -1을 출력해야 한다.

문제를 3단계로 요약하자면 위처럼 정리할 수 있습니다.

---

어떻게 접근해야할까?

문제를 문장으로 길게 적어놔서 그렇지 결국 문제에서 원하는 것은 3과 5만으로 목표값을 만드는 것입니다.

여기서 단지 연산 횟수를 최소화하라는 조건만 추가되었을 뿐입니다.

그럼 어떻게 문제를 풀어나갈 수 있을까요?

15라는 값을 3과 5만으로 만들어야 한다고 가정해봅시다.

15를 5로 나누면 몫은 3이 됩니다.
15를 3으로 나누면 몫은 5가 됩니다.

이 때 최소 연산 횟수는 15를 5로 나누는 것입니다.

왜냐하면 15에서 5를 3번 뺀다면 0이 되기 때문입니다.

좀 더 나아가서 3과 5의 공배수가 아닌 값을 만드는 것을 가정해봅시다.

18을 3과 5로 만들어야 합니다.

18을 3으로만 연산한다면, 6번의 뺄셈을 거쳐야 합니다.

하지만 18을 5로 최대한 뺀 나머지를 3으로 뺀다면 어떻게 될까요?

18을 5로 최대한 뺀다면 뺄셈은 3번이 될 것이고, 나머지는 3이 될 것입니다.
이 후 3을 다시 3으로 뺀다면 뺄셈은 1번이 될 것이고 나머지는 0이 됩니다.

즉, 우리는 18이라는 숫자를 3과 5를 이용해서 4번의 연산으로 만들 수 있습니다.

이 과정에서 우리는 목표한 숫자를 큰 수로 최대한 뺀 뒤 나머지를 작은 수로 뺀다면 최소한의 연산 횟수로 구할 수 있다는 것을 알 수 있습니다.

---

코드로 작성해보자

먼저 위에서 설명한 것을 식으로 간단하게 보겠습니다.

18 / 5 = 3 ... 3 -> 연산 횟수: 3
3 - 3 = 0 -> 연산 횟수: 1

연산 횟수 합: 4

이런 식이 만들어지게 됩니다.

이제 이것을 코드로 변환하면,

int count = 0;
int N = 18;

count = N / 5;
N = N % 5;
count = count + N / 3;;

System.out.print(count);

이런 연산 과정을 거칠 수 있습니다.

하지만 만약, 목표값이 5로 나누어 떨어진다면 그 때의 몫이 최소 연산이 되게 됩니다.

왜냐하면 가장 큰 수로 나누는 것이 최소 연산이기 때문입니다.

이 점을 고려해서 조건까지 추가해보겠습니다.

int count = 0;
int N = 18;

if(N % 5 == 0) {
	System.out.print(N / 5);
}
else {
	count = N / 5;
    N = N % 5;
	count = count + N / 3;
}

System.out.print(count);

이렇게 코드를 작성할 수 있습니다.

하지만 우리는 목표값을 5로 나눈 나머지가 3이 아닐 경우도 생각해야합니다.
그럴 경우에는 연산을 반복해서 최소 횟수를 구해야 합니다.

따라서 현재 코드에 반복문을 추가해보겠습니다.

int count = 0;
int N = 18;

while(N >= 0) {
	if(N % 5 == 0) {
    	count = count + N / 5;
        break;
    }
    else if(count == 0) {
    	count = N / 5;
        N = N % 5;
    } else {
    	count = count + N / 3;
    }
}

System.out.print(count);

이런 코드가 나오게 됩니다.

하지만 이 코드에는 문제가 있습니다.

만약 목표값을 5로 나눈 나머지가 3의 배수가 아니라면, N은 항상 0이 됩니다.

나머지가 2라면, 2 / 3 = 1이 나오고 반복문이 돌면서 1 / 3 = 0이 되게 됩니다.

그래서 우리는 코드를 조금 수정해줄 필요가 있습니다.

int count = 0;
int N = 18;

while(N >= 0) {
	if(N % 5 == 0) {
    	count = count + N / 5;
        break;
    }
    else if(count == 0) {
    	count = N / 5;
        N = N % 5;
    } else {
    	N = N - 3;
        count++;
    }
}

System.out.print(count);

목표값에서 계속 3을 빼주고 연산 횟수를 1씩 증가시킨다면 우리가 원하는 값을 얻을 수 있게 됩니다.

---

전체 코드

이제 위에서 작성한 코드에 문제의 나머지 조건과 입력, main함수, class이름을 추가해주고, 비효율적인 부분을 수정해보겠습니다.

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) {
                count += N / 5;
                break;
            }
            N -= 3;
            count++;
        }
        
        if (N < 0) {
            count = -1;
        }

        System.out.println(count);
    }
}

이번 문제의 전체 코드입니다.

기존 코드의

else if(count == 0) {
    count = N / 5;
    N = N % 5;
} else {
    N = N - 3;
    count++;
}

위 코드를 굳이 조건문을 사용하지 않아도 되므로 조건문을 삭제하였습니다.

N -= 3;
count++;

이렇게 두 줄을 추가한 것만으로도 충분히 연산이 가능합니다.

왜냐하면 5로 나눈 나머지에서 3을 빼거나, 3을 빼서 5의 배수로 만든 후에 5로 나누거나 결과가 똑같기 때문입니다.

그래서 목표값 N이 5의 배수가 아니면 3을 빼도록 하여 5의 배수로 만든 후 5로 나누도록 작성하였습니다.

또한, 3과 5로 표현할 수 없는 수는 -1을 출력하도록 문제에서 제시했기 때문에

if (N < 0) {
	count = -1;
}

위 부분을 추가하였습니다.

마지막으로 코드를 한 번 쭉 설명하자면,

1. int N = sc.nextInt();으로 목표값을 입력 받습니다.

2. int count = 0; 아직 연산 전이므로 연산 횟수를 0으로 초기화해줍니다.

3. while (N >= 0) 목표값 N이 0보다 같거나 클 때까지만 반복되게 설정합니다.

4. if (N % 5 == 0) 연산 전에 먼저 N이 5의 배수라면,

5. count += N / 5; N / 5의 몫을 count에 더한 후,

6. break;를 통해 반복문을 종료합니다.

7. 그렇지 않다면, N -= 3; 이 코드를 통해 N에서 3을 뺍니다.

8. 이 때 count를 count++;를 통해 1씩 증가시킵니다.

9. N이 0보다 작아질 때까지 4 - 8의 과정을 반복합니다.

10. 반복문이 끝난 후 if (N < 0) 이 조건으로 N이 음수인지 판단합니다.

11. N이 음수라면 3과 5로 만들 수 없는 수라는 의미이므로 count = -1;로 count에 -1을 저장합니다.

12. System.out.println(count); 마지막으로 코드의 결과를 출력하고 프로그램은 종료됩니다.

---

마무리

이렇게 단계적으로 문제에 접근해서 코드를 작성하고 원하는 결과값이 나온 후에 효율적으로 수정하는 연습을 한다면, 문제 푸는 실력이 늘 것 같습니다.

감사합니다. 😌