[백준 9084] 동전 (JAVA)

백준 9084번 문제 - 동전

9084번: 동전

---

문제 분석

 

 

• 가지고 있는 동전 종류를 통해 해당 값을 계산할 수 있는 모든 방법의 수를 출력하라

---

해결 키 포인트

 

• 방식 1 (정말 너무 어려웠음 ,,,)
  • 나누어떨어지는 경우, 해당 수가 될 수 있는 수를 저장해놓고
  • 나누어 떨어진 값^될 수 있는 수 개수
  • ex) 1 2로 100을 만들어야할 때, 1이될 수 있는 수 나 빼고 0개, 2가 될 수 있는 수 나 빼고 1개
          sum = 100/1^0 + 100/2^1 = 51
  • 이 방식의 문제 ! 안나눠떨어지는 값들 처리를 어떻게 해야할지 모르겠다 ~!
  • 다음이 도전한 방식의 코드

            long sum = 0;
            int [] dp = new int [N];
            for (int n=0;n<N;n++) {
                int coin = coins.get(n);
                if(M % coin == 0) {
                    for(int i=0;i<n;i++) {
                        if(coin % coins.get(i) == 0)
                            dp[n]++;
                    }
                    sum += Math.pow(M/coin, dp[n]);
                }
            }

            bw.write(sum + "\n");

 

• 방식 2 (해설 검색)
  • M원까지 해당 동전을 가지고 만들 수 있는 개수를 dp에 저장하여 dp[M] 출력
  • i부터 M까지 구할 수 있는 값 구하기
    dp[i] = i번째 수를 만들 수 있는 경우의 수 개수
  • https://songsunbi.tistory.com/67 ← 참고

---

코드

 

import java.awt.desktop.QuitEvent;
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 테스트 케이스 수
        int T = Integer.parseInt(br.readLine());

       // 케이스 실행
        for(int t=0;t<T;t++) {
            // 동전 가지 수
            int N = Integer.parseInt(br.readLine());

            ArrayList<Integer> coins = new ArrayList<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 동전 입력
            for (int n=0;n<N;n++) {
                coins.add(Integer.parseInt(st.nextToken()));
            }

            // 만들어야할 금액 M
            int M = Integer.parseInt(br.readLine());

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

            // i부터 M까지 구할 수 있는 값 구하기
            // dp[i] = i번째 수를 만들 수 있는 경우의 수 개수
            for (int n=0;n<N;n++) {
                for(int i=coins.get(n);i<=M;i++) {
                    dp[i] += dp[i - coins.get(n)];
                }
            }

            bw.write(dp[M] + "\n");
        }
        bw.flush();
        bw.close();
    }
}