JAVA 백준 문제풀이 (24) 11047: 동전 0

 

 

그리디 알고리즘 첫번째 문제이자 그리디 알고리즘을 전혀 몰라도 풀 수 있는 문제이다.

하지만 우리는 백준 정답 맞추기가 궁극적인 목표가 아니기 때문에 그리디 알고리즘에 대해 간단히 알아보자.

 

그리디 알고리즘(greedy algorithm)은 그 이름이 굉장히 잘 어울리는 알고리즘으로, 뒷 일은 신경쓰지 않고 무조건 당장 택할 수 있는 최선만을 선택하는 알고리즘이다.

 

예를 들어 우리가 편의점에서 아르바이트를 하고 있는데 4800원을 받았고, 최대한 효율적으로 돈을 거슬러주려면 어떻게 해야할까?

당연히 천원짜리 네 장, 오백원 한 개, 백원짜리 세 개를 거슬러주면 될 것이다.

그런데 컴퓨터에게 이것을 어떻게 명령할 수 있을까?

 

무조건 제일 큰 단위의 돈을 택해서 나눌 수 있을 때까지 나누고, 그 다음 단위의 돈을 택해서 또 나눌 수 있을 때까지 나누고, 그 다음 단위의 돈을 택해서 나눌 수 있을 때까지 나누면 된다. 

 

그런데 중요한 점은 그리디 알고리즘이 만능이 아니라는 것이다.

일단 당장 우리 앞에 주어진 문제부터 그리디 알고리즘을 바탕으로 풀어보자.

 

 

 

 

 

import java.util.*;
import java.io.*;


public class temp {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int kind_coin = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        int coinArr[] = new int[kind_coin];

        for (int i=0; i<kind_coin; i++) { // 동전 종류 (오름차순)
            coinArr[i] = Integer.parseInt(br.readLine());
        }
        // 여기까지 유저 입력값 처리

        // 그리디 알고리즘
        int result = 0;
        for (int i=coinArr.length-1; i>=0; i--) {
            while ( T - coinArr[i] >= 0 ) {
                result += (T / coinArr[i]); // 계산하려는 값 T를 coinArr[i]로 나눌 수 있는 횟수
                T %= coinArr[i]; // 나눈 나머지를 다시 반복문 돌려서 0이 될 때까지
            }
        }
        System.out.println(result);
    }
}

 

 

쩝.. 문제 풀이 자체는 쉬워서 더 이야기 할 게 없다.

위에서 하던 얘기인 그리디 알고리즘이 늘 최선이 아니라는 것에 대해 이야기해보자.

 

만약 이 코드에 동전 종류(3)과 구하려는 합(1200)을 입력하고 동전 종류(100,400,500)을 입력했다고 가정해보자.

결과는 몇이 나올까?

 

당연히 500으로 두 번 나누고 100으로 두 번 나눌테니 4가 나올 것이다.

하지만 가장 효율적인 횟수는? 400으로 세 번 나누는 것이 가장 적은 횟수로 1200을 나눌 수 있다.

 

이처럼 그리디 알고리즘은 늘 매번의 선택에 최선의 결과를 택할 뿐 전체를 고려하지 않기 때문에 알고리즘 적용 전 반례를 먼저 찾아봐야 한다.