[백준 2293번] 동전 1

문제 링크: 2293번 동전 1

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

 

dp[k]는 k원을 만드는 경우의 수를 나타낸다. 이 때 coins[0](엄밀히는 동전 중 임의의 한 개)만을 사용한다면, k가 coins[0]의 배수일 때에는 모두 1가지이므로 if k%coins[0]==0 dp[k]=1을 수행한다. 그 후, coins[1:](엄밀히는 처음에 선택한 동전을 제외한 다른 동전들)에 대해서, dp[k] += dp[k-coin]을 수행한다. coin만을 이용해서 만들 수 있는 경우의 수는 이미 dp[k]에 포함되어 있고, dp[k-coin]은 k-coin원에다가 coin을 이용해 coin만큼을 더해서 k를 만드는 경우의 수이므로 이 둘을 더해준다.

 

import java.util.Arrays;
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        Set<Integer> set = new HashSet<Integer>();

        for (int i = 0; i < n; i++)
            set.add(sc.nextInt());

        n = set.size();

        int[] coins = new int[n];
        int idx = 0;
        for (int item : set)
            coins[idx++] = item;

        // Arrays.sort(coins);
        /* 동전의 크기는 관계없다.
           어차피 어떤 동전으로 금액을 만드냐의 차이이지
           얼만큼의 금액을 만드냐의 차이가 아니기 때문이다. */

        int[] dp = new int[k+1];
        for (int i = 0; i <= k; i++)
            if (i % coins[0] == 0)
                dp[i] = 1;

        if (n==1) {
            System.out.println(dp[k]);
            System.exit(0);
        }

        for (int c = 1; c < n; c++) {
            dp[0] = 1;
            int coin = coins[c];
            for (int money = 1; money <= k; money++)
                if (coin <= money)
                    dp[money] += dp[money-coin];
        }

        System.out.println(dp[k]);
    }
}