Boj -14196/ java/ greedy

백준 14196번 greedy 알고리즘의 대표적인 문제다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int money = Integer.parseInt(br.readLine());
        int money5 = money/5;
        if(((money - money5)%2 != 0)&(money5 !=0)  ){ //만일 5가 최대인데 홀수라면
            money5--;
        }
        if((money - money5*5)%2 !=0){
            System.out.print(-1);
        }
        else {
            int money2 = (money - money5 * 5) / 2;
            System.out.print(money5 + money2);
        }


    }
}

 

간단히 설명해서 greedy 알고리즘은 그 순간에 최적의 선택을 하는 것. 여기서는 당장 5원을 최대한 늘리는 것이 최선의 선택.

 

문제를 너무 복잡하게 풀었다. 아래처럼 반복문을 활용해 풀 수 있었을 것이다.

int answer = -1;
for(int i=money/5;i>=0;i--){
            if((money - (5 * money5))%2 == 0){	//5원을 i개 쓰고 2원으로 거스를 수 있을 때
                answer = i + (money - (5 * i))/2;	//동전의 개수 저장
                break;	//가장 먼저 거슬러 줄 때가 최소 개수
            }
        }