[3-1] 거스름돈 - 이것이 취업을 위한 코딩 테스트다 with 파이썬

그리디 알고리즘(Greedy Algorithm: 탐욕법, 욕심쟁이 알고리즘)

의미: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

어떠한 문제를 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘

매 순간 가장 좋아 보이는 것을 선택하고, 그 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다.

 

예제 3-1: 거스름돈

500, 100, 50, 10원 무한히 존재.

손님에게 거슬러 줘야 할 돈: N원

거슬러 줘야 할 동전의 최소 개수 구하는 문제

단, N은 항상 10의 배수

// 거스름돈
package ch3;

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

public class Ex3_1 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // N
        int cnt = 0; // 최소한의 동전 개수

        // 거슬러 줘야 할 동전의 최소 개수 구하는 코드
        if (n >= 500) { // 500원
            cnt += n / 500;
            n %= 500;
        }
        if (n >= 100) { // 100원
            cnt += n / 100;
            n %= 100;
        }
        if (n >= 50) { // 50원
            cnt += n / 50;
            n %= 50;
        }
        if (n >= 10) { // 10원
            cnt += n / 10;
        }
        
        System.out.println(cnt);
    }
}