[백준/BOJ] 2839번 설탕 배달 (java)

백준 온라인 저지(BOJ) 2839번 설탕 배달

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

2839번: 설탕 배달

* 사용언어 : java, 자바

 

1. 문제

설탕 N킬로그램을 배달 (3 ≤ N ≤ 5000)

3킬로그램과 5킬로그램 봉지가 있음

최대한 적은 개수의 봉지로 배달하려 함

 

봉지의 최소 개수를 출력

(정확하게 N킬로그램이 안된다면 -1 출력)

 

2. 풀이

단계별로 풀어보기를 순서대로 해결했다면, 처음으로 만나는 알고리즘 문제다운 문제입니다.

복잡해보이지만 규칙을 찾는다면 어렵지 않게 풀 수 있습니다.

 

봉지를 최소로 사용하려면 5킬로그램 봉지를 최대한 많이 사용해야합니다.

저는 처음에 5 단위 주기로 규칙이 있을 것이라 보고 N이 6, 11, 16인 경우를 생각해보았습니다.

 

1) N == 6

봉지의 최소 개수 : 2 (3킬로 2개)

2) N == 11

봉지의 최소 개수 : 3 (3킬로 2개, 5킬로 1개)

3) N == 16

봉지의 최소 개수 : 4 (3킬로 2개, 5킬로 2개)

 

이 경우를 보면서 5개 주기로 규칙이 있다는 것을 알게되었습니다.

규칙을 자세히 알아보기 위해 3부터 19까지 봉지 최소 개수를 확인해보았습니다.

 

(n : 설탕의 총 무게, count : 봉지 최소 개수)

 

정확하게 만들 수 없는 4킬로와 7킬로 제외하고 보면,

5개 주기로 값이 반복되고 있습니다.

n = 5, 10, 15 (n % 5 == 0) 의 count 값은 n / 5 와 같습니다.

n = 6, 11, 16 (n % 5 == 1) 그리고 8, 13, 18 (n % 5 == 3) 의 count 값은 n / 5 에 1을 더한 값과 같습니다.

n = 12, 17 (n % 5 == 2) 그리고 9, 14, 19 (n % 5 == 4) 의 count 값은 n / 5 에 2를 더한 값과 같습니다.

 

이러한 규칙을 활용하여 코드를 작성했습니다.

 

* switch문에서 아래와 같이 작성하면, 1과 3인 경우 해당 실행문이 실행됩니다.

case 1:
case 3:
	// 실행문

 

3. 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();

		int count = n / 5;
		switch (n % 5) {
		case 0:
			System.out.println(count);
			break;
		case 1:
		case 3:
			System.out.println(count + 1);
			break;
		case 2:
			if (count < 2) System.out.println(-1);
			else System.out.println(count + 2);
			break;
		case 4:
			if (count < 1) System.out.println(-1);
			else System.out.println(count + 2);
			break;
		}
	}
}