daily pastebin goal
15%
SHARE
TWEET

Untitled

a guest Feb 14th, 2018 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class CoinChange {
  4.    
  5.     public static long change(int dollars, int[] coins) {
  6.         if (dollars == 0) { return 1; }
  7.         if (coins.length == 0) { return 0; }
  8.        
  9.         long[] store = new long[dollars+1];
  10.         store[0] = 1;
  11.        
  12.         for (int coin : coins) {
  13.             for (int i = 0; i < store.length-coin; i++) {
  14.               // 각 단위 별로 만들 수 있는 경우의 수
  15.                 store[i+coin] += store[i];
  16.             }
  17.         }
  18.         return store[dollars];
  19.     }
  20.    
  21.     public static long makeChange(int[] coins, int money) {
  22.         long[] DP = new long[money + 1];
  23.         DP[0] = (long) 1;
  24.         for(int coin : coins) {
  25.             for(int j = coin; j < DP.length; j++) {
  26.                 DP[j] += DP[j - coin];
  27.             }
  28.         }      
  29.         return DP[money];
  30.     }
  31.    
  32.     public static void main(String[] args) {
  33.         Scanner in = new Scanner(System.in);
  34.         int n = in.nextInt();
  35.         int m = in.nextInt();
  36.         int coins[] = new int[m];
  37.         for(int coins_i=0; coins_i < m; coins_i++){
  38.             coins[coins_i] = in.nextInt();
  39.         }
  40.        
  41.         System.out.println(change(n, coins));
  42.     }
  43. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top