LINK

BOJ : 동전2

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

전략

dp[i]=i금액을 최소 화폐개수로 만드는 수.
i=> 금액
dp[i]=Min(dp[i],dp[i-하나의 금액]+1)

예시

2,3,5원 금액이 주어질경우.
dp[0]=100001 로 초기화 후에.
2원으로 k까지의 금액을 만드는 경우는
2원을 뺀 idx 에서 기존에 있는 화폐를 만들 수 있는 최소화페의 개수보다 새롭운 화페의 가치로 인하여 만들수 있는 최소 개수+1중에 누가 더 작은지 비교를 해야한다.

2원 가치로 이룰 수 있는 최소 화페의 개수를 구한뒤 3원의 가치로 이룰 수 있는 최소화페의 개수를 갱신한다. 6원 같은 경우 2원짜리 3개를 이용하여 구할 수 있다. 즉 dp[6-2]+1로 구한 값이 였다. min(3,dp[6-3]+1) 로 비교를 하게 되면서 2원짜리 동전 3개,3원짜리 2개중에 당연히 3원짜리로 6원을 만드는 화페의 개수가 작으므로 갱신되나다.

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int k=Integer.parseInt(st.nextToken());
        int coin[]=new int[k+1];
        Arrays.fill(coin,100001);
        int arr[]=new int[n];
        for (int i = 0; i < n; i++) {
            st=new StringTokenizer(br.readLine());
            arr[i]=Integer.parseInt(st.nextToken());
        }
        coin[0]=0;
        for (int i = 0; i < n; i++) {
            int COIN=arr[i];
            for (int j = COIN; j <k+1 ; j++) {
                    coin[j]=Math.min(coin[j],coin[j-COIN]+1);
            }
        }
//        System.out.println(Arrays.toString(coin));
        if(coin[k]!=100001)
            System.out.println(coin[k]);
        else
            System.out.println(-1);
    }