[JAVA] 백준_14916 거스름돈

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

📌 문제 탐색하기

n원을 2원짜리와 5원짜리 동전으로 동전 개수를 최소로 거슬러주는 문제이다.
거슬러 줄 수 없는 경우 -1을 출력해야한다. 

📌 가능한 시간복잡도

입력받은 n의 값이 홀수이거나 5이하로 나누어 떨어지는 수가 아니면 2원짜리 동전을 사용해서 n을 주여야함. 
매번 반복문에서 n의 값이 2씩 감소하기때문에 최대 반복 횟수는 n/2이다. 
큰 동전을 사용할 수 없는 경우 2원짜리 동전을 계속 사용해야함. 
따라서 가능한 시간복잡도 O(N)이다. 

📌 코드 설계하기

그리디 알고리즘 적용
큰 동전을 최대한 많이 사용하고 큰 동전 사용이 더 이상 불가능한 경우 2원 동전을 하나씩 추가하면서 가능한 조합을 찾는다.

📌 정답 코드

import java.io.*;

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;
                System.out.println(count);
                return;
            }
            n -= 2; 
            count++;
        }
        System.out.println(-1); 
    }
}