[BaekJoon/Java] 백준 2839번 설탕배달

문제 요약 설명

설탕 무게 N이 주어졌을 때, 5키로 봉지와 3키로 봉지에 나누어 담는다고 한다. 이 때 봉지수를 가장 적게 사용해서 나누어 담아라

아이디어

5kg봉지가 가장 많이 담을 수 있기 때문에 먼저 5kg봉지에 담을 수 있을 만큼 담고 나머지를 3kg봉지에 담는 식으로 진행하면 된다. 예외적으로 5kg봉지에 담았으나 나머지가 3kg봉지에 담을 수 없다면 5kg봉지수를 줄여가는 식으로 진행 할 수 있다.

풀이

1. 먼저 입력으로 들어온 N을 5로 나눈다. 이 값은 5kg봉지에 최대한 담았을 때 몇개를 사용하는지 알 수 있게 해준다.
2. 반복문으로 1번에 나눈 값부터 0까지 반복한다. 이 때 0까지 하는 이유는 5kg봉지에 담고 나머지가 3kg봉지에 담기지 않는다면 5kg봉지를 하나도 안쓰고 3kg봉지만 써야하는 경우도 발생한다.
   ex) 9라는 숫자는 5kg봉지를 하나라도 쓰면 담을 수 없지만 3kg 봉지 3개로 담을 수 있다.
3. 반복문 내에서 5kg봉지에 담고 난 나머지가 3kg으로 나누어 떨어진다면 그 때 사용한 봉지수를 카운팅 한다.
4. cnt의 초기값은 2000으로 설정되어 있는데 입력의 최댓값이 5000으로 정해지기 때문에 5000을 3으로 나누어서 최대한 많은 봉지를 사용하면 1666 정도의 값이 나온다. 그래서 임의로 2000이라는 값을 주고 만약 5kg와 3kg에 나누어 담을 수 없는 무게라면 cnt값이 변하지 않고 최종적으로 2000이라는 값이 그대로 전달될것이므로 그럴 경우에는 -1을 출력한다.

코드

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

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 cnt = 2000;
        int loop = N / 5;
        int total = N;
         for(int i = loop; i >= 0; i--) {
             int tmpCnt = i;
             if ((N - (5 * i)) % 3 == 0) {
                 int three = (N - (5 * i)) / 3;
                 tmpCnt += three;
                 if (tmpCnt < cnt) {
                     cnt = tmpCnt;
                 }
             }
         }
         if(cnt == 2000) {
             System.out.print(-1);
         } else {
             System.out.print(cnt);
         }
    }
}