[BOJ] 백준 14916 거스름돈

출처: https://www.acmicpc.net/problem/14916

 Input 
　 

 Output 

　

거스름돈을 2원과 5원을 활용하여 최대한 적은 수의 동전으로 거슬러주는 방법을 구하는 문제

문제 조건상 (1 <= n <= 100,000) 거슬러 줄 수 없는 경우가 존재하는데,

n = 1 혹은 3일 때이다. (2원, 5원으로 거슬러줄 수 없기 때문이다.)

그 외는 5원을 최대한 활용하는 코드를 구현하면 된다.

---

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        // 거스름돈을 입력받는다.
        int n = Integer.parseInt(sc.next());
        
        // 거슬러 줄 수 있는지 확인한다. (1,3인지 확인한다.)
        if(n - 5 < 0 && !(n % 2 == 0)) {
            System.out.println("-1");
            return;
        }
        
        // 5원짜리를 최대한 늘려가며 거슬러준다.
        int min = 0;
        if(n % 2 == 0) { // 2로 나누어 떨어진다면 2원짜리로만 해서 초기값 세팅
            min = n / 2;
        }else { // 5원이 적어도 1개 필요한 경우(5이상의 홀수)
            // 필요한 2원짜리의 개수
            min = (n - 5) / 2;
            // 일단 5원짜리를 한개 사용
            min++;
        }
        
        // 5의 개수를 최대한 늘려본다.
        int cnt_of_5 = 0;
        int cnt_of_2 = 0;
        while(true) {
            // target을 원래의  n으로 초기화
            int target = n;
            // 5원 짜리 개수를 한개 늘려본다.
            cnt_of_5++;
            target = target - 5 * cnt_of_5;
            
            // 더 이상 5의 개수를 늘려봤자 무의미하므로 답을 출력하고 종료
            if(target < 0) {
                // 지금까지 구한 것 중에 저장된 최소 동전의 개수를 출력
                System.out.println(min);
                return;
            }
            
            // 최대한 늘린 5원짜리 개수와 나머지 2원짜리로 거슬러 줄 수 있을 때
            if(target % 2 == 0 ) {
 
                cnt_of_2 = target / 2;
                // System.out.println("5원짜리 개수: " + cnt_of_5 + ", 2원짜리 개수: " + cnt_of_2);
                
                // 2원짜리와 5원짜리의 총 개수
                // 지금까지의 최소값과 비교해 더 작은 값을 저장한다.
                if(min > cnt_of_5 + cnt_of_2) {
                    min = cnt_of_5 + cnt_of_2;
                }
            }
        }
    }
}