11047

동전 0 : https://www.acmicpc.net/problem/11047

참조 :  https://st-lab.tistory.com/143

 

그리디 풀이 법이 참조 사이트에 있는데, 동전의 종류에 따라 예외가 있는 것으로 알고 있다.

참조에 따르면, 동전들이 배수관계에 있을 경우에만 그리디로 풀 수 있는 것으로 보인다.

만약 코인의 종류가 5, 3, 1이면 해당 그리디 방식은 오류가 발생할 것이다. 

 

성능 제약에 문제가 없고, 코인의 종류에 따라 오답확률이 있는 수식을 쓸 바에야.

냅색을 통해 정확하게 값을 구하는 것이 낫지 않나 하는 생각이 든다.

 

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

public class Main {

	static int N, K;
	static int [] coin, price;
	static boolean DBG = false;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		coin= new int [N];
		price= new int [K+1];
		for (int i = 0 ; i < N ; i ++) {
			coin[i] = Integer.parseInt(br.readLine());
		}
		
		for  ( int i = 0 ; i < N ; i++) {			
			for ( int j = coin[i] ; j <= K ;  ++j) {
					price[j] = price[ j - coin[i]] + 1;
			}
		}
		
		System.out.println(price[K]);
	}


}