[백준/Java] 9084번 : 동전

문제

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

동전의 가지 수 N

1, 5, 10, 50, 100, 500원으로 M원을 만드는 모든 방법의 수를 출력하라.

풀이

d[i][j] = i번 동전까지 사용해서 금액 j원을 만들 수 있는 경우의 수

//점화식
if(j < coin[i])
	dp[i][j] = d[i-1][j]; //현재 동전보다 가격이 낮아서 현재 동전을 못 쓰는 경우
else
	dp[i][j] = d[i-1][j] + d[i][j-coin[i]]; //현재 동전을 안 썼을 때의 개수 + 현재 동전도 함께 고려하며 만들 때의 개수

 

예) 1원, 2원, 5원으로 10원을 만들 수 있는 경우의 수

코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int t = Integer.parseInt(br.readLine());
        for(int i=0; i<t; i++){

            int n = Integer.parseInt(br.readLine()); //동전의 가지 수
            st = new StringTokenizer(br.readLine()); //각 동전의 가격
            int price = Integer.parseInt(br.readLine()); //만들어야 할 가격

            int[] coins = new int[n]; 
            for(int k=0; k<n; k++){
                coins[k] = Integer.parseInt(st.nextToken());
            }

            int[][] d = new int[n+1][price+1]; //dp배열의 0행을 0으로, 0열을 1로 채움 (margin 설정)
            Arrays.fill(d[0], 0);
            for(int k=1; k<=n; k++){
                d[k][0] = 1;
            }

            for(int j=1; j<=n; j++){
                for(int j2=1; j2<=price; j2++){
                	//점화식 구현
                    if(j2 < coins[j-1])
                        d[j][j2] = d[j-1][j2];
                    else
                        d[j][j2] = d[j-1][j2] + d[j][j2-coins[j-1]];
                }
            }
            System.out.println(d[n][price]);
        }
    }
}