이것이 취업을 위한 코딩테스트다 - 그리디(1)

그리디 알고리즘 = 탐욕법이라고 말한다.

어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

 

대표 예제. 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 단, 거슬러줘야할 돈 N은 항상 10의 배수이다.

 

최소단위로 동전 개수를 구해야 하므로 가장 큰 화폐단위부터 돈을 거슬러 준다는 생각을 하면 문제를 해결할 수 있다.

 

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

public class J_3_1 {
    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;

        int[] coinTypes = {500, 100, 50, 10};

        for(int i = 0; i < 4; i++){
            int coin = coinTypes[i];
            count += N / coin;
            N %= coin;
        }
        System.out.println(count);
    }
}

 

 

 

 

 

 

 

참고한 책 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 by 나동빈

참고한 GitHub : https://github.com/ndb796/python-for-coding-test