백준 2839번: 설탕 배달, 5로 나눈 나머지에서 규칙 찾기

봉지 수를 나머지로 나눠 봅니다

백준 2839번은 설탕 Nkg을 3kg 봉지와 5kg 봉지로 정확히 나눌 때 필요한 최소 봉지 수를 구하는 문제입니다. 정확히 나눌 수 없다면 -1을 출력합니다.

1부터 25 정도까지 두 종류의 봉지 수를 적어 보며 규칙을 찾았습니다. 1kg, 2kg, 4kg, 7kg은 만들 수 없습니다. 문제의 입력은 3 이상이므로 코드에서는 4와 7을 따로 처리했습니다.

5로 나눈 몫과 나머지

a = N / 5, b = N % 5로 두면 다음과 같이 나뉩니다. 앞에서 본 4와 7은 먼저 제외합니다.

나머지 b	봉지를 구성하는 방법	전체 봉지 수
0	5kg 봉지 a개	a
1	5kg 봉지 하나를 빼고, 남은 6kg을 3kg 두 봉지로 구성	2 + (a - 1) = a + 1
2	5kg 봉지 두 개를 빼고, 남은 12kg을 3kg 네 봉지로 구성	4 + (a - 2) = a + 2
3	5kg 봉지 a개에 3kg 한 봉지 추가	1 + a = a + 1
4	5kg 봉지 하나를 빼고, 남은 9kg을 3kg 세 봉지로 구성	3 + (a - 1) = a + 2

나머지가 1이나 3이면 a + 1, 2나 4이면 a + 2로 묶을 수 있습니다. 이 규칙을 그대로 조건문으로 옮겼습니다. 당시에는 동적 계획법이라고 불렀지만 이전 계산 결과를 배열에 쌓지 않고 나머지에 따라 봉지 수를 직접 계산하는 방식입니다.

제출 코드

Java

import java.io.*;

class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        int a = N / 5;
        int b = N % 5;

        int result = 0;

        if (N == 4 || N == 7) {
            result = -1;
        } else {
            if (b == 0) {
                result = a;
            } else if (b == 1 || b == 3) {
                result = a + 1;
            } else if (b == 2 || b == 4){
                result = a + 2;
            }
        }

        bw.write(String.valueOf(result));
        bw.flush();
    }
}