문제 번호 2839번 : 설탕 배달 - JAVA [자바]

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

2839번: 설탕 배달

 

문제 설명

 

Nkg의 설탕을 3kg 봉지와 5kg의 봉지에 나누어 담되 봉지수가 최소가 되게 해 달라는 문제입니다.

간단하게

(3*x) + (5*y) = N인데 x+y의 최솟값을 구하라는 문제입니다.

정말 많은 풀이법이 있지만 가장 직관적인 방법과 가장 간결한 방법의 코드 두 가지를 소개하겠습니다.

 

문제 풀이

 

1. 직관적인 풀이

저는 직관적인 풀이를 더 좋아합니다. 알아보기도 쉽고 유지 보수에 도움이 되기 때문이죠. 

일단 이 문제 변수 명을 보여드리겠습니다.

int sugarWeigth = sc.nextInt(); //설탕 무개
int minWegith = 5000; //최소 봉지 개수
boolean flag = false; //flag

문제에 조건에 설탕 무개는 최대 5000라고 되어 있음으로 봉지수는 적어도 5000개를 넘지 못합니다. 그럼으로 5000을 초기화 해줍니다.

이 문제를 보고 가장 먼저 든 생각은 5kg으로 최대한 채우고 그다음에 3kg를 채우면 된다는 거였죠

근데 또 5kg으로 나눠지지 않는데 3kg으로만 나눠지게 되는 경우도 있고

오로지 5kg으로 나눠지는 경우도 있죠 그런 경우에는 따로 조건을 세워서 예외 처리를 해주어야 합니다.

예외 처리는 나중에 생각하도록 하고 먼저 5kg으로 최대한 채우고 그다음에 3kg을 채울 때 최소 봉지를 어떻게 구할 수 있을지 생각해 봅시다.

저는 제가 생각하는 방법대로 로직을 짜는 걸 좋아하는데요여기서는 두 가지 예가 중요합니다.18kg을 예를 들어보면 5*3 =. 15고 18-15=3이니깐 총 4 봉지가 최소 값이겠네?라고 계산을 했습니다.11kg에 경우 5*2=10이고 나머지는 1이어서 3kg으로 들 수 없지만 11-5=6kg이고 이러면 3kg으로 나눠짐으로 11kg도 가능하게 됩니다.그렇다면 조건으로 일단 5로 나눈 나머지가 3으로 나누어 떨어진 다는 조건이 있어야 3kg과 5kg을 섞었을 때 최소 값이 나옵니다. 두 번째로는 11kg의 경우 11/5나 11%5를 하게 되면 무조건 적으로 몫을 2로 계산함으로 /를 사용해서는 안됩니다. 5의 배수만큼 빼기를 돌려서 뺀 결과가 3으로 나누어지는지 확인을 해야 되는 거죠.두 가지를 조건을 적용하면 다음 과 같은 조건이 나옵니다.

for(int i = 1; i < (sugarWeigth/5)+1; i++ ) {
    if((sugarWeigth-(5*i))%3 == 0) {
        if(minWegith > i+((sugarWeigth%(5*i))/3)){
            minWegith = i+((sugarWeigth-(5*i))/3);
        }
        //System.out.println("혼합[" +i + "] : " + minWegith);
        flag = true;
    }
}

for문은 5로 나눈 숫자에 +1만큼을 돌려주면 됩니다. 여기서 i는 5의 배수를 전체 kg수에서 빼주는 역할을 할 것입니다. 예를 들어 18kg이면 18-5/18-10/18-15 이렇게 총 3번을 돌려 줘야 하는 것이죠 이렇게 3번을 돌린 후에 5kg의 몇 봉지가 제일 숫자가 적은 지 확인 할 것입니다. 18-5=13 임으로 3으로 나눠지지 않아 조건에 제외될 것이요. 18-10=8역시 3으로 나눠지지 않아 조건에서 제외 될 것입니다. 18-15는 3으로 나눠 떨이짐으로 조건에 들어오고 i+1 즉 3+(3/3)의 값을 minWeigth에 초기화 해 줍니다.이렇게 하면 11의 경우도 값을 구할 수 있습니다.11 - (5*1) = 66/3 = 21+2 = 3(최소 봉지수)11 - (5*2) = 11%3 != 0 임으로 조건에 들어가지 못합니다.flag는 나중에 뒤에서 설명하겠습니다.

 

이제 예외 처리를 해주어야 합니다. 바로 3으로 나누어 떨어지는 경우와 5로 나누어 떨어지는 경우입니다.

if(sugarWeigth%3 == 0) {
    if(minWegith > sugarWeigth/3) {
        minWegith = sugarWeigth/3;
    }
    flag = true;
    //System.out.println("3kg: " + minWegith);
}
if(sugarWeigth%5 == 0) {
    if(minWegith > sugarWeigth/5) {
        minWegith = sugarWeigth/5;
    }
    flag = true;
    //System.out.println("5kg: " + minWegith);
}

질문 : 🙋‍♂️ 3kg과 5kg으로만 나눈 무개보다 3kg과 5kg이랑 같이 나눈 무개의 봉지 개수가 더 작으면 어떻게 하나요?걱정할 필요 없습니다. 18kg같은 경우 이미 minWegith는 4kg으로 위에서 초기화 되어 있습니다. 그래서 3kg으로 나눠 떨어지는 곳에서 6이라는 결과를 출력해 봤자 최솟값을 비교하는 조건에서 걸리게 됩니다.

 

마지막으로 3kg과 5kg으로 봉지를 나눠 담을 수 없을 때 -1를 출력하는 예외를 조건을 걸겠습니다

if(flag == false) {
    minWegith = -1;
}

 

네 flag가 여기서 사용됩니다. 3kg과 5kg으로도 못만들면 flag가 false로 그대로일 테니(모든 조건에 flag를 true로 바꿔준것을 볼 수 있습니다.) false면 -1을 넣어주면 됩니다.

 

방법1 정답

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
		
		int sugarWeigth = sc.nextInt();
		int minWegith = 5000;
		boolean flag = false;
		
		for(int i = 1; i < (sugarWeigth/5)+1; i++ ) {
			if((sugarWeigth-(5*i))%3 == 0) {
				if(minWegith > i+((sugarWeigth%(5*i))/3)){
					minWegith = i+((sugarWeigth-(5*i))/3);
				}
				//System.out.println("혼합[" +i + "] : " + minWegith);
				flag = true;
			}
        }
        if(sugarWeigth%3 == 0) {
            if(minWegith > sugarWeigth/3) {
                minWegith = sugarWeigth/3;
            }
            flag = true;
            //System.out.println("3kg[" +i + "] : " + minWegith);
        }
        if(sugarWeigth%5 == 0) {
            if(minWegith > sugarWeigth/5) {
                minWegith = sugarWeigth/5;
            }
            flag = true;
            //System.out.println("5kg[" +i + "] : " + minWegith);
        }
		
		
		if(flag == false) {
			minWegith = -1;
		}
		
		System.out.println(minWegith);
		
    }
}

 

2. 수학적인 풀이

개인적으로 그렇게 좋아하진 않지만 코드가 간결해지고 가독성이 높아진다는 장점이 있습니다.

둘 다 할 줄 알아야겠죠.

https://st-lab.tistory.com/72

[백준] 2839번 : 설탕 배달 - JAVA [자바]

다음 블로그 설명을 참고하시면 됩니다.

 

간단히 설명하면

5로 나눠지는 봉지개수는 n/5를 하면 최소 봉지 개수가 나옵니다.

그럼 5의 배수가 아닌 나머지를 계산하면 됩니다.

5x + 1 인 경우에는 5의 배수를 빼면 무조건 6이 남습니다. 그래서 3kg으로 채울 수 있습니다.

5x + 3 인 경우에서도 5의 배수를 빼면 무조건 3이 남습니다. 이 역시 3kg으로 채울 수 있습니다.

계산해 보시면 아시겠지만 두 가지 경우에는 n/5의 +1을 해주면 됩니다.

5x + 2 인 경우에는 7을 제외하고 5의 배수를 빼면 12가 남게 됩니다. 그럼 3kg의 4봉지로 채울 수 있습니다.

5x + 4 인 경우에는 5의 배수를 빼면 9가 남습니다. 그럼 3kg의 3봉지로 채울 수 있습니다.

 

사실 원리는 간단합니다. 해당 kg의 5씩 더하면 한봉씩식 늘어난다는 원리입니다.

 

정답은 해당 블로그를 참고 하시면 됩니다.😊