[백준] 2839: 설탕 배달

 

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int count = 0;
        while (N > 0) {
            if (N % 5 == 0) {
                count += N / 5;
                N = 0;
            } else {
                N -= 3;
                count++;
            }
        }

        if (N < 0) {
            System.out.println(-1); // 정확하게 N킬로그램을 만들 수 없는 경우
        } else {
            System.out.println(count); // 상근이가 배달하는 봉지의 최소 개수 출력
        }
    }
}

 

입력값이 5로 나눠지면 그 몫이 배달 횟수가 되고

그렇지 않다면 3씩 빼면서 5로 나눠지는지 확인한다.

 

이때 N에서 3을 감소시키면서 배달 횟수는 한 번 증가한다.

 

 

입력값이 4 같이 계산 불가능한 경우

0보다 크니 반복문에 들어왔지만 5로 나눠지지 않아 

반복문을 빠져나왔을 때는 N에 -2가 들어있을 것이다.

따라서 N이 0보다 작아졌기 때문에 -1을 출력한다.

 

 

 

그리디 알고리즘

: 현재 상황에서 최적의 방안을 고르는 알고리즘