(백준) 동전 - 9084 [java]

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

9084번: 동전

 

🐢 설명

다이나믹 프로그래밍 문제로 N번째 결과를 구하기 위해 N - 1번째 결과를 구하는 점화식이 필요하 문제이다. 이런 DP문제는 테이블을 만들어서 접근하는 것이 가장 좋으며 메모이제이션 기법을 활용해야한다.

 

N개의 동전으로 M원을 만들기 위한 가짓수를 출력하는 문제이므로 DP[M] : M원을 만들 수 있는 총 가짓수 형태로 풀어보자.

 

2, 3, 5원 동전이 존재하고 만들려는 금액이 10원인 경우

표를 채울 때 참고할 점은 5원짜리 동전은 1 ~ 4원은 어짜피 못만드므로 확인할 필요가 없다는 점이다.

또한, X원을 만드는 개수는 ( 이전 동전으로 만든 개수 ) + { ( X - 현재 동전 )의 개수 } 를 추가하는 방식으로 진행하면 된다.

동전 \ 금액	1	2	3	4	5	6	7	8	9	10
2원	X	1	X	1	X	1	X	1	X	1
3원	X	X	1	1	1	2 (1 + 1)	1	2 (1 + 1)	2 (0 + 2)	2(1+1)
5원	x	x	x	x	2 (1 + 1)	2	2 (1 + 1)	3 (2 + 1)	3 (2 + 1)	4 (2 + 2)

이런식으로 C원 동전에서 X원을 만드는 횟수를 채울 때 DP[X원] += DP[X - C원] 의 형태로 갱신시켜 주면 된다.

 

🐢코드

//package Gold이상문제_정리;

import java.io.*;
import java.util.*;

public class Main {
    static int T;
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        T = Integer.parseInt(br.readLine());

        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            int[] coins = new int[N];
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                coins[i] = Integer.parseInt(st.nextToken());
            }
            int M = Integer.parseInt(br.readLine());

            dp = new int[M + 1];
            dp[0] = 1;

            for (int coin : coins) {
                for (int m = coin; m <= M; m++) {
                    dp[m] += dp[m - coin];
                }
            }
            sb.append(dp[M]).append("\n");
        }
        System.out.print(sb);
    }
}

 

🐢 마무리

DP를 풀때 테이블을 만들어야함을 꼭 명심하자!!! 또한 1차원 배열을 만들지 2차원 배열을 만들지, 무엇을 기준을 잡아야할지 곰곰히 생각해서 설계하자.