[BOJ] 2839번 : 설탕 배달 (JAVA/자바)

문제

---

알고리즘 고민

N을 5와 3으로 더해서 구할 수 있는지에 대한 문제이다. 처음으로 바로 든 생각은 N에서 3씩 빼주면서 5로 나누어 나머지 없이 떨어진다면 그때의 3을 뺀 갯수와 5로 나눈 몫을 더해주면되겠다는 생각이 들었다. 이 문제에서는 N의 최대값이 5000이고 시간제한도 그렇게 어렵지 않기 때문에 통과할 수 있었다. 다만 조건이 조금 더 어렵게 설정된다면 통과를 못할 코드이기에 조금 더 고민을 해보았다.

 

먼저 1,2,4,7의 경우는 3과 5를 이용해서 만들 수가 없다. 그렇기 때문에 그때는 -1을 출력해주고, 나머지의 경우에는 모두 5와 3으로 만들 수 있었다. 먼저 5의 수를 N/5를 통한 몫으로 구하고 그때 나눈 나머지를 구한다. 나머지가 0인 경우에는 정확히 모두 5로 N을 완성했기 때문에 끝이 나게 되고, 나머지가 1~9인경우에는 추가적인 개수를 더해줘야한다.

나머지 값	1	2	3	4
추가 값	(1+5) / 3 = 2	(2+10) / 3 = 4	(3) / 3 = 1	(4+5) / 3 = 3

나머지 값이 나올 수 있는 수로는 5로 MOD 를 했기 때문에 1,2,3,4가 나올 수 있다. 1일때는 5짜리 봉투 한개를 가져와서 3으로 나누어 주면 2개, 2일때는 2개를 가져와서 3으로 나누면 4개, 3일때는 3으로 나누어서 1개 4일때는 봉투 한개를 가져와서 3으로 나누어 주면 3개가 각각 추가된다.

1일때는 5에서 하나  빠지고 2봉투가 추가 되기때문에 아까 N/5 값에 +1을 하고, 2일때는 -2+4 이기 때문에 +2를 해주고, 3일때는 그냥 +1, 4일때는 -1+3이기 때문에 +2가 된다. 추가적인 코드는 주석으로 밑에 써두었다.

---

JAVA Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

//        if (N == 1 || N == 2 || N == 4 || N == 7) {
//            System.out.println(-1);
//        } else {
//            int pack5 = N / 5;
//            int remain = N % 5;
//            if (remain == 0) {
//                System.out.println(pack5);
//            } else {
//                if (remain == 1 || remain == 3) {
//                    System.out.println(pack5 + 1);
//                } else {
//                    System.out.println(pack5 + 2);
//                }
//            }
//        }

        int cnt = 0;
        while (true) {
            if (N % 5 == 0) {
                cnt+=(N/5);
                break;
            } else if (N < 3) {
                cnt=-1;
                break;
            }
            cnt++;
            N-=3;
        }

        System.out.println(cnt);
    }
}