📌 문제

[2839] 설탕 배달

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

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

⬇️ 입력

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

⬇️ 출력

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

💡 코드

✅ n이 3과 5로 정확히 나누어 떨어지면서 값이 최소인 경우를 찾아야 한다. n을 3으로 나눈 횟수를 cnt에 저장하고, 3으로 나누고 남은 나머지 num을 다시 5로 나눈 횟수를 cnt에 더해준다. 이 때, 최종 단계인 num / 5를 마쳤을 때 나머지가 0으로 정확하게 나누어 떨어지면 이를 최솟값에 저장한다.

이를 이중 for문을 통해 n/3번 실행하였을 때, 최종 min 값이 초기값인 Integer.MAX_VALUE 이면 나누어 떨어지지 않았다는 의미이므로 -1 을, 다른 값을 가진다면 최솟값 min을 최종 정답으로 출력한다.

❌ 아래 코드에 예제를 입력했을 땐 다 정답이였는데 오답 처리가 됐다,, 다시 보니 아래 코드는 n을 n/3 ~ 1번 나누는 경우만을 탐색하고 3으로 0번 나누는 경우, 즉, 5로만 나누는 경우를 탐색하지 않는다!

30을 입력하는 경우, 최솟값은 5키로 6봉지이지만, 5로만 나누는 경우를 고려하지 않아 3키로 5봉지 + 5키로 3봉지 = 8봉지가 최솟값이 된다!

import java.io.*;
public 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 min = Integer.MAX_VALUE;
		
		for(int i=n/3;i>0;i--) {
			int num = n; int cnt = 0;
			
			for(int j=i;j>0;j--) {
				num -= 3;
				cnt++;
			}
			
			cnt += num/5;
			
			if(num % 5 == 0) 
				min = cnt < min ? cnt : min;
		}
		
		if(min == Integer.MAX_VALUE) bw.write("-1");
		else bw.write(min + "");

		br.close();
		bw.close();
	}
}	

✅ 이중 for문의 바깥쪽 for문의 조건식에 등호를 하나 추가하여 i >=0으로 고쳐주면 해결된다! ➕ 5와 3의 자리를 바꿔도 결과는 같다!

import java.io.*;
public 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 min = Integer.MAX_VALUE;
		
		for(int i=n/5;i>=0;i--) {
			int num = n; int cnt = 0;
			
			for(int j=i;j>0;j--) {
				num -= 5;
				cnt++;
			}
			
			cnt += num/3;
			
			if(num % 3 == 0) 
				min = cnt < min ? cnt : min;
		}
		
		if(min == Integer.MAX_VALUE) bw.write("-1");
		else bw.write(min + "");

		br.close();
		bw.close();
	}
}