백준 알고리즘 - 2839 설탕 배달

www.acmicpc.net/problem/2839

2839번: 설탕 배달

 

  백준 알고리즘의 '설탕 배달' 입니다.

 

  사실 전형적인 그리디 알고리즘으로 보입니다만, 생각보다 처리해주어야할 예외가 많습니다.

 

  이 문제에서는 상근이가 정확하게 N킬로그램을 배달해야 하는데, 담을 수 있는 봉지가 3킬로그램짜리와 5킬로그램짜리 밖에 없다고 합니다. 그래서 만일 이 둘로 담을 수 있는 용량이라면 최소한의 봉지의 갯수를, 담을 수 없다면 -1을 출력하는 문제입니다.

 

  딱 봤을 때 드는 생각은 'N을 5로 나눠서 나머지는 3으로 담으면 되겠군.' 이런 생각이 듭니다.

  

  하지만 5로 나눴을 때, 나머지가 0이면 상관 없지만, 1, 2, 3, 4 일 때에는 각각의 경우에 맞춰서 값을 나눠주어야 합니다. 게다가 초반의 1, 2, 4, 7는 아예 나눠지지 않아서 따로 처리를 해주어야 합니다.

 

  저는 3과 5의 공배수인 15까지 확인하기 위해서 1에서 15까지 종이에 적어서 하나하나 지워가면서 풀었습니다. ^^

  

 

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

public class Main_BJ_2839_설탕배달 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int count = 0;
		
		int N = Integer.parseInt(br.readLine());
		
		if(N % 5 == 0) count = N / 5;
		else if(N % 5 == 3) count = (N / 5) + 1;
		else if(N % 5 == 1 || N % 5 == 4) {
			if(N == 1 || N == 4) {
				count = -1;
			}else {
				count = (N / 5) - 1 + (N - ((N / 5) - 1) * 5) / 3;
			}
		}
		else if(N % 5 == 2) {
			if(N == 2 || N == 7) count = -1;
			else{
				count = (N / 5) - 2 + (N - ((N / 5) - 2) * 5) / 3;
			}
		}
		
		System.out.println(count);
	}
}