[JAVA] 백준 9084번 : 동전

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

---

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

public class Main {
    static int[] coins, dp;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
            coins = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int M = Integer.parseInt(br.readLine());
            dp = new int[M + 1];
            dp[0] = 1;
            for (int c : coins) {
                for (int base = M - c; base >= 0; base--) {
                    if(dp[base] == 0) continue; //의미 없음
                    for (int i = 1; i <= M / c; i++) {
                        int newVal = base + c * i;
                        if (newVal > M) break; //이후는 계속 범위 초과할테니
                        dp[newVal] += dp[base];
                    }
                }
            }
            //M만드는 모든 방법의 수
            sb.append(dp[M]).append("\n");
        }
        System.out.print(sb);
    }
}

💡 DP

풀이

 

전형적인 배낭 채우기 문제이다. 근데 난 배낭 문제가 싫다. ...어쩌라고...

어쨌든, dp/배낭채우기 문제 종류는 배열의 인덱스나 구성을 어떻게 설정하는지가 문제 풀이의 핵심같다

 

전에 풀었던 #2624. 동전 바꿔주기 문제를 참고해서 거의 동일한 방식으로 풀었다.

1차원 배열을 만들고 >>> dp[a] = b : 총 금액 a를 만들 수 있는 동전 조합의 수 b 가지그 뒤, 동전 단위 금액 c에 대해서, 베이스 금액 M - c 부터 시작해 0까지 줄여나가며 +c가 가능한 조합을 모두 구함-> 동전 c가 1개 ~ M/c개 들어가는 경우의 수 더해줌 (M을 넘는 경우 제외)

경우의 수를 결정하는 요인은 총 합 금액에 따라 가능한 경우의 수가 달라진다
-> 인덱스가 값이 됨, 값 별로 가능한 경우의 수 구함

 

---

다른 경우를 생각해보면, 그냥 모든 동전 종류에 대해서 coin[i] ~ M 까지의 경우에 대해 누적합 해가는 방식으로 하면 더 간단할 것 같다

coin = new int[N+1]; // 1부터 N까지 동전 종류 저장
dp[0] = 1;
for(i-> 1 ~ N) //동전 종류 1부터 N번째 동전의 경우에 대해 구함
    for(j-> coin[i] ~ M) //가치 coin[i] 부터 M까지 경우에 대해 가능한 경우의 수 누적해나감
        dp[j] += dp[j - coin[i]];
sout(dp[M]);