[백준] 9084 : 동전

문제

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

 

 

 

입출력

3
2
1 2
1000
3
1 5 10
100
2
5 7
22

 

501
121
1

---

아이디어

 

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

 

 

코드 

 

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

public class Main {
	static int T;
	static int[] coins;
	static int M;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		for (int t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine()); // 동전의 가지수
			coins = new int[N];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int n = 0; n < N; n++) {
				coins[n] = Integer.parseInt(st.nextToken());
			}
			M = Integer.parseInt(br.readLine()); // 구해야할 금액
			int[] dp = new int[M + 1];
			dp[0] = 1;
			for (int coin : coins) {
				for (int m = coin; m <= M; m++) {
					dp[m] += dp[m - coin];// dp[m] += dp[m-coins[n]]// 금액m을 만드는 가지수
				}
			}
			System.out.println(dp[M]);
		}
	}
}