[백준] 14916 - 거스름돈 (Java)

[백준] 14916 - 거스름돈 (Java)

문제

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

풀이/후기

그리디 알고리즘을 사용하여 풀이한다.

2원과 5원을 이용해 가장 적은 동전으로 거슬러야 하기 때문에 5원으로 먼저 계산한다.

5로 나누어 떨어지지 않으면 N에서 2원을 빼주면서 cnt를 늘려주는 것이 포인트였던 것 같다.

코드

package Greedy;

import java.io.*;

public class Problem14916 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int cnt = 0;
        
        while (N > 0){
            //System.out.println(N);
            if (N % 5 == 0){
                cnt += N / 5;
                N = N % 5;
            } else {
                N = N - 2;
                cnt++;
            }
            
        }

        if (N < 0) {
			System.out.println(-1);
		} else {
			System.out.println(cnt);
		}
        
    }
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/4b87c8045b0c66327c04494747afb28fa0b1fe19

참고