[Algorithm][JAVA] 백준 11047번: 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

---

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다.

이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다.

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

코드

import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt(); //N 입력 받기
		int K = in.nextInt(); //K 입력 받기
		
		int[] coin = new int[N]; 
		
		for(int i = 0; i < N; i++) {
			coin[i] = in.nextInt();
		}
		
		int count = 0; //필요한 동전 개수
 
 		//동전 개수의 최솟값을 구하는 것이므로, 동전이 오름차순으로 입력되므로 N -1부터 시작
		for(int i = N - 1; i >= 0; i--) { 
			if(coin[i] <= K) { //현재 동전가치가 K보다 작거나 같아야 구성 가능
				count += (K / coin[i]); 
				K = K % coin[i];
			}
		} //K=0일 때 반복문 종료
        
		System.out.println(count);
	}
}

쉽게 풀 수 있을 줄 알았는데 막상 코드를 작성하다 보니 잘 안 되어서 결국 구글링 했다...

구글링을 통해 이 문제가 그리디 알고리즘을 이용하는 문제라는 것을 알게 되었다.

또 하나의 알고리즘을 알아간다 ~

 

그리디 알고리즘 개념과 코드 링크: https://st-lab.tistory.com/143

 

결과