[JAVA] 백준 11047번 : 동전 0

 

---

 

• 생각

동전을 정렬해준 뒤 가장 큰 M보다 작은 동전부터 맞춰나가며 몇개의 동전이 필요한지 세주면 최소의 동전 수로 M을 맞출 수 있을 것이다. 이 문제에선 오름차순으로 알아서 입력이 되니 뒤의 index부터 확인을 해주면 될 것 같다.

 

• 코드

정답 코드 : 가장 큰 동전부터 맞는 수만큼 count를 세주어가며 M을 맞춰 나갔다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, M, count;
	static int[] array;

	public static void main(String[] args) throws Exception {
		SetData();
		FindMinCount();
		System.out.println(count);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		count = 0;
		array = new int[N];

		for (int i = 0; i < N; i++) 
			array[i] = Integer.parseInt(br.readLine());
		
	}

	public static void FindMinCount() {
		// 가장 큰 돈부터 채워나가면 최소의 동전 수로 원하는 값을 채울 수 있다.
        for(int i = N-1; i>=0; i--){
            if(M>=array[i]){
                count += M/array[i];
                M = M%array[i];
            }            
        }
	}

}