[문제 풀이] 백준 11047번 동전 0 JAVA

문제

 

  문제접근 방법   

해당 문제는 동전의 개수와 만들려고하는 합 두 값을 입력받고 각각 동전의 가치를 입력받아 동전을 조합해 만들려고 하는 합을 만드는데 필요한 동전의 최소 개수를 출력하는 프로그램을 작성하는 문제이다.여기서 각각의 동전의 가치는 오름차순으로 주어지고  배수관계이다.

해당 문제를 보고 바로 떠오른 알고리즘이 하나있다. 바로 탐욕법이라고도 불리는 그리디 알고리즘이다. 

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만을 고르는 방법으로 최적의 해를 보장해야 사용할 수 있다.

본인이 본 문제에서 발견한 최적의 해 보장 요소는 바로 배수관계라는 것이다. 500원 100원 10원이 존재한다면 

배수관계이기 때문에 가장 큰 동전부터 더해줘야 최소 개수를 구할 수 있다. 만약 800원을 만들어야하는데

동전이 500원 400원 100원이라면 그리디 알고리즘 기준 500원 1개와 100원 3개로 총 4개의 동전을 사용할 것이다.

하지만 400원 2개로도 800원을 만들수 있다. 이렇게 본 문제에서는 배수관계로 최적의 해를 보장하므로 그리디 알고리즘을 사용하는것이 적합하다고 판단하였다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int k=s.nextInt();
        int cnt=0;
        int change[]=new int[n];
        for(int i=0;i<n;i++){
            change[i]=s.nextInt();
        }
        
        for(int i=n-1;i>=0;i--){
            cnt+=(k/change[i]);
            k=k%change[i];
        }
        System.out.print(cnt);
    }
}

사실 그리디 알고리즘을 활용해야한다고 바로 생각이 들었다면 구현 자체는 난이도가 쉬운편이라고 생각된다. 

간단하게 만들어야하는 값 k를 가장 큰 동전으로 나누고 몫은 cnt에 더해주어 카운트해주고 

나머지느 k에 다시 넣어 주는 흐름이다.

 

  마무리  

사실 예전에도 해당 문제를 풀이한 적이 있었다. 그때는 본 문제가 그리디 알고리즘을 활용하는 문제라는 것을 모르고도 쉽게 풀이하였었다. 하지만 운이 좋았을뿐 위에서 설명했듯이

확신과 명확한 이유가 존재하지는 않았다. 다만 본능적으로 큰값을 먼저 소비하면 좋겠다라 생각해 그렇게 했을뿐이었다.

하지만 이제는 최적의 해를 보장해야하는데 이게 배수관계라서 보장하고 그래서 그리디알고리즘으로 문제 해결이 가능하다.

라는 것을 명확하게 알게되는 문제였다.