백준 9084 동전 (Java)

1. 문제 링크

9084번: 동전

 

2. 문제 및 입출력예제

 

3. 문제 풀이

1. dp로 하는데 money[만들 수 있는 가격]에 경우의 수를 저장한다.
2. 동전마다 만들 수 있는 경우의 수를 money 배열에 더한다.
3. money 배열은 해당 동전으로 만들 수 있는 인덱스부터 시작해야 하기 때문에 j=i부터 시작하게 했다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;

public class Main {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for(int t=0;t<T;t++) {
			int N = Integer.parseInt(br.readLine());
			int[] coin = new int[N];
			String[] split = br.readLine().split(" ");
			for(int i=0;i<N;i++) {
				coin[i] = Integer.parseInt(split[i]);
			}
			int M = Integer.parseInt(br.readLine());
			
			int[] money = new int[M+1];

			money[0] = 1;
			for(int i : coin) {
				for(int j=i;j<M+1;j++) {
					money[j] += money[j-i];
				}
			}
	
			sb.append(money[M]).append("\n");
			
		}
		System.out.println(sb);
	}
}