문제링크

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

구현방법

최소의 값을 구하는 거기때문에 5원을 기준으로 생각하고 만약 5로 나눈 나머지가 0일경우 나눈 값을 coin에 넣어주고 N을 나눈 나머지 값으로 갱신하고, 만약 나눈 나머지가 0이 아닐경우 2를 빼고나서 나눠지는 경우가 있기 때문에 2를 빼주고 다시 5로 나눈 나머지가 0이 되는지 체크합니다.

그후 N이 0보다 작을 경우는 5원과 2원으로 거스름돈을 줄 수 없는 경우이기 때문에 -1를 출력하고 리턴하고

아닌 경우 coin을 출력해줍니다.

구현알고리즘

그리디알고리즘

CODE

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

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());

        //1원 3원
        int coin = 0;
        //동전의 개수가 최소가 되게 -> 값이 큰 동전으로 최대한 주고 남은 것을 2원짜리로 준다.
        while(N > 0){
            //5로 나눈 나머지가 0일때 -> 그냥 나머지면됨.
            if(N % 5 == 0){
                coin += N / 5;
                N %= 5;
            }else {
                N -= 2;
                coin += 1;
            }
        }
        //N이 0보다 작은경우 -> 거스름돈을 줄수 없는 경우.
        if(N < 0) {
            System.out.println(-1);
            return;
        }

        System.out.println(coin);
    }
}