[백준 JAVA] 9084 동전

!!!!! 핵심 : 다이나믹프로그래밍사용시는 bottom-up 이든 top-down이든
모든요소를 작게 나누고 쌓아간다는 생각을 하자.
(재귀함수 , 메모이제이션사용)

[문제]
우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.
동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.
편의를 위해 방법의 수는 231–1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없다.

[출력]
각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	private static int coin_count[]; //총나올코인갯수
	private static int coins[][]; //코인들 2차원배열
	private static int price[]; //만들어야될금액

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int test_count = scanner.nextInt();
		
		//메모리할당
		coin_count = new int[test_count];
		coins = new int[test_count][]; //1차원할당
		price = new int[test_count];
		
		for(int i = 0 ; i < test_count ; i ++) {
			coin_count[i] = scanner.nextInt(); //동전가짓수
			coins[i] = new int[coin_count[i]]; //2차원할당
			scanner.nextLine();
			StringTokenizer st = new StringTokenizer(scanner.nextLine());
			
			for(int j = 0 ; j < coin_count[i] ; j++) 
				coins[i][j] = Integer.parseInt(st.nextToken()); //동전종류
			
			price[i] = scanner.nextInt(); //만들금액
		}
		scanner.close();


		for (int i = 0; i < test_count; i++) {
			System.out.println(make_money(coins[i], price[i]));
		}
		
		
		
	}
	private static int make_money(int coin[] , int money) {
		int d[] = new int[money+1]; //d[0] 은 무시
		d[0] = 1;
		
		for(int i = 0 ; i < coin.length ; i++) {
			for(int j = coin[i] ; j <= money ; j++) {
				d[j] += d[j - coin[i]];
			}
		}
		
		return d[money];
	}

}

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