[백준/JAVA] 2839 : 설탕 배달 ( 기본 수학 1 )

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다.

설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다.

예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만,

5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

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

입력

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

출력

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

 

예제입력	예제출력
18	4
4	-1
6	2
9	3
11	3

 

 

⭕ 풀이

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int sugar = Integer.parseInt(br.readLine());
        
        int fiveCnt = sugar/5;
        int threeCnt = 0;
        int remain = sugar%5;
        
        while(fiveCnt!=-1){
            
            if(remain%3==0){
                threeCnt=remain/3;
                break;
            }else{
                fiveCnt--;
                remain+=5;
            }
        }
        System.out.println(fiveCnt==-1?-1:fiveCnt+threeCnt);
    }
}

 

✅ 풀이과정

 

주어진 설탕을 5로 나눴을때 5라면 너무 좋겠지만 아닐테고

5로 나눈뒤 나머지가 3이라면 너무 좋겠지만 이또한 아닐경우의 수가 더 많을것이다.

 

따라서 5kg 설탕봉지를 셀 fiveCnt에 주어진 sugar/5를 할당하고 남은만큼을 담을 remain에는 sugar%5 를 담아둔다.

그리고 while문 안에서 remain을 3으로 나눈 나머지가 0이된다면 

위에 언급한 5로 나눈뒤 나머지가 3이되는 상황일것이다.

충족한다면 3kg 설탕봉지를 셀 threeCnt 에 remain/3을 하고 반복문을 탈출하면된다.

예를들어 설탕이 8kg였다면 fiveCnt 는 1이었고 while문안에서 5로나눈나머지 3을 품고있던 remain을 3으로 나누면 0일것이다.그럼 threeCnt 에도 1을 할당하고 탈출하면 fiveCnt=1 threeCnt=1 로 총 2봉지가 연산된다.

 

그렇지만 else로 가는 경우도 당연히 따져봐야한다.

예를들어 설탕이 11kg였다면 fiveCnt는 2였고 while문안에서 5로 나눈나머지 1을 품고있던 remain을 3으로 나누면 0이 아니다

그럼 5kg봉지를 하나 줄여서 다시 계산해본다. 5kg봉지를 하나 줄였다는건 1을 품고있던 remain에도 5kg가 늘어야한다는것이다.

else문에서 이 과정을 처리해준다. five--; remain+=5;

그럼 fiveCnt는 1이되었고 remain은 5가 더해져 1에서 6이 된상태다.

if문 remain%3==0 을 충족하므로 remain/3인 2를 threeCnt에 할당하고 탈출한다.

탈출하면 fiveCnt 는 2였다가 한봉지를 줄였으니 1  threeCnt는 remain을 3으로 나눈 2 총 3봉지가 연산된다

 

하지만 5kg와 3kg로 나눠담을 수 없는 경우도 있다.

예제에서 나온 4의 경우, 혹은 7도 마찬가지이다.

7로 예를들어보자 fiveCnt = 1 인상태 remain은 2인 상태로 while문에 들어간다.

if문을 충족시키지못해 else로 가서 fiveCnt--;  remain+=5 를 수행한다.

fiveCnt = 0 remain=7 

fiveCnt가 0임과 동시에 remain이 3의 배수라면, 다시말해 주어진 sugar가 5의 배수는 아니면서 3의 배수라면

상근이는 경우의수중 가장 설탕봉지를 많이 들고가게된다.

 

하지만 위의경우 fiveCnt=0 remain=7 

remain도 3으로 나누어지지않는다. 그럼 결국 else문을 한번더 실행해 fiveCnt-- 를 실행하면

fiveCnt = -1이 되며 fiveCnt가 -1이 되었다는말은

결국 모든경우의수를 탐색해보았고 마지막까지가서 전부 3kg로 때려박아보았지만 딱떨어지지 않았다는 말이된다.

그러므로 fiveCnt = -1라면 -1을 출력하고

아니라면? 즉 어떻게든 딱떨어지게 만들어서 break문을 만나 탈출한거라면?

fiveCnt+threeCnt 를 출력한다.

 

 

 

 

 

-출처

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