[백준] 9084 동전 - Java

 

 

 

문제 출저

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

9084번: 동전

 

 

 

문제 풀이

동전의 종류 n개와 동전으로 만들어야 할 금액 m이 주어집니다.

주어진 동전으로 금액 m을 만들 경우의 수를 구해야 합니다. 

 

 

DP를 통해 풀었습니다. 

크기가 m+1인 1차원 배열을 만듭니다.

dp = new int[m+1] 

 

이 dp 배열은 0부터 m까지 금액을 만들 수 있는 경우의 수를 저장합니다. 

dp[0] 인 0원은 동전을 하나도 안 사용하는 방법만 있으니 1을 선언합니다.

dp[0] = 1 

 

이 후 가지고 있는 동전의 종류만큼 반복문을 시행합니다. 

점화식은 다음과 같습니다. 

coins = new int[n+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
    coins[i] = Integer.parseInt(st.nextToken());
}


dp = new int[m+1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (j - coins[i] >= 0) dp[j] = dp[j] + dp[j - coins[i]];
    }
}

 

현재 동전 coins[i]을 사용하여 금액 j를 만드는 경우의 수는 dp[j - coins[i]] 를 만드는 경우의 수와 동일합니다. 금액 j - coins[i]에 현재 동전을 추가하면 j가 되기 때문입니다. 

 

이런 식으로 2중 반복문을 돌면서 dp를 완성하고 dp[m] 출력해 정답을 구합니다. 

 

 

 

소스코드

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

/*
동전
https://www.acmicpc.net/problem/9084

 */

public class Main {

    static int t;
    static StringBuilder sb;
    static int n; // 동전의 가짓수
    static int[] coins; // 동전 종류
    static int m; // 만들어야 하는 금액
    static int[] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        t = Integer.parseInt(br.readLine());
        sb = new StringBuilder();

        while(t-->0) {
            n = Integer.parseInt(br.readLine());
            coins = new int[n+1];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= n; i++) {
                coins[i] = Integer.parseInt(st.nextToken());
            }
            m = Integer.parseInt(br.readLine());
            solution();
        }

        System.out.println(sb);

    }

    // 문제 풀이
    public static void solution() {
        dp = new int[m+1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (j - coins[i] >= 0) dp[j] = dp[j] + dp[j - coins[i]];
            }
        }

        sb.append(dp[m]).append("\n");
    }



}