146. 11047(동전 0) - 자바

import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		Integer[] coinList = new Integer[N];
		int cnt = 0;

		for (int i = 0; i < N; i++) {
			coinList[i] = sc.nextInt();
		}

		Arrays.sort(coinList, Collections.reverseOrder());

		for (int val : coinList) {
			if (val > K) {
				continue;
			} else {
				if (K == 0) {
					break;
				}

				cnt += (K / val);
				K %= val;

			}
		}
		
		System.out.println(cnt);
	}
}

문제요약

주어진 동전 리스트를 최소로 사용하여 가치에 맞게 만드시오

설명

그리디 알고리즘의 대표 문제이다.

그리디 알고리즘에 대해서는 아래를 참고하자

https://smhope.tistory.com/384

[알고리즘 | 자료구조] 그리디 알고리즘(Greedy Algorithm)

 

간단히 설명하면 주어진 상황에 가장 최적인 것을 선택해서 문제를 해결하는 것이다.

 

위 문제에서는 동전리스트를 최소로 사용하고자 하므로 동전 가격이 가장 큰 것 부터 고르면 된다.

Integer[] coinList = new Integer[N];

Integer로 값을 받은 이유는 Collections.reverseOrder() 를 실행하기 위해서이다.

올림차순 Arrays.sort는 int형에서도 받지만,  Collections.reverseOrder() 의 옵션을 주게 되면 int 형으로는 받을 수 없고 Integer를 사용해야 한다.

 

Arrays.sort(coinList, Collections.reverseOrder());

 

주어진 동전리스트를 내림차순으로으로 정리하였다.

 

		for (int val : coinList) {
			if (val > K) {
				continue;
			} else {
				if (K == 0) {
					break;
				}
				cnt += (K / val);
				K %= val;
			}
		}

매번 가장 큰 동전 부터 시작해서 반복하는 방법도 있지만, 그렇게 하면 시간이 매우 오래걸린다.

따라서 한번 선택한 동전을 가치에서 나눠준 몫을 카운터에 저장한다.

 

예를들어 4200의 가치를 맞추고자 할 때 동전리스트 중에서 1000원이 가장 큰 수라면 1000원이 4장 필요하다.

따라서 4200에서 1000을 나눠 나온 몫 4를 카운트에 저장하고, 4200에서 1000을 나눈 나머지 200은 다음으로 넘긴다.