백준 11047 [동전 0] - JAVA

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

11047번: 동전 0

 

풀이

동전갯수의 최솟값을 찾아야한다.

 

1. 금액이 큰 동전부터 선택한다.

2. 1번의 동전을 최대한 많이 선택한다.

3. 입력받은 금액만큼 동전을 선택했는지 확인한다. 그렇지 않다면 1번부터 다시 수행한다.

 

소스코드

package algorithm.greedy;

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

/**
 * 동전0
 */
public class Q11047 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String inputArr[] = br.readLine().split(" ");
		
		int N = Integer.parseInt(inputArr[0]);
		int K = Integer.parseInt(inputArr[1]);
		int coinArr[] = new int[N];
		int nCoinCnt = 0;
		
		for(int nIdx = 0 ; nIdx < N ; nIdx++) {
			coinArr[nIdx] = Integer.parseInt(br.readLine());
		}
		
		while(true) {
			/*1.선택절차*/
			//현재상태에서 최적의 해를 찾는다
			for(int nIdx = coinArr.length - 1 ; nIdx >= 0 ; nIdx--) {
				/*2.적절성 검사*/
				//선택된 해가 문제의 조건을 만족하는지 검사한다.
				int nReturnCoin = K / coinArr[nIdx];
				if(nReturnCoin > 0) {
					K -= nReturnCoin * coinArr[nIdx];
					nCoinCnt += nReturnCoin;
					break;
				}
			}
			
			/*3.해답 검사*/
			//문제가 해결되었는지 검사한다.
			if(K == 0) {
				System.out.println(nCoinCnt);
				break;
			}
		}
		
	}

}