99클럽 코테 스터디 14일차 TIL 그리디(거스름돈)

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

<아이디어>

동전의 개수를 최소로 사용하려면 5원을 최대한 사용해야한다.

그리고 2원으로 나눠져야 하므로 5원을 가지고 짝수로 만들어야 함을 알 수 있다.

따라서. n이 홀수일 때와 짝수일 때를 나누어 홀수면 5를 최대의 홀수번으로 나누고, 짝수면 5를 최대의 짝수번으로 나누고자 했다.

 

*** 5미만이 들어오면 짝수일 때는 2로 나누어지지만, 홀수일 때는 낼 수 있는 방법이 없으니 -1을 출력해야한다.

package STUDY.Week02;

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

public class Day14_BOJ_14916_거스름돈 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());

        if(n < 5 && n % 2 != 0) System.out.println(-1);
        else{
            int cnt = 0;
            // 5원 짜리 계산
            int tmp = (int) n / 5;
            if(n % 2 != 0){
                if(tmp % 2 == 0) {
                    cnt = tmp - 1;
                    n = n - (5 * (tmp - 1));
                }else{
                    cnt = tmp;
                    n = n - (5 * tmp);
                }
            }else{
                if(tmp % 2 != 0) {
                    cnt = tmp - 1;
                    n = n - (5 * (tmp - 1));
                }else{
                    cnt = tmp;
                    n = n - (5 * tmp);
                }
            }
            // 2원짜리 계산
            cnt += (int) n / 2;
            System.out.println(cnt);
        }
    }
}