[이코테] DP - 효율적인 화폐구성 - JAVA

최영환·2022년 11월 9일
0

이코테

목록 보기
19/24
post-thumbnail

💡 문제

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.

입력

  • 첫째 줄에 N,M이 주어진다(1<= N <= 100, 1<= M <= 10,000)
  • 이후의 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐의 가치는 10,000보다 작거나 같은 자연수이다.

출력

  • 첫째 줄에 경우의 수 X를 출력한다.(불가능할 때는 -1을 출력한다)

💬 입출력 예시

입력

2 15
2
3

출력

5

📌 풀이(소스코드)

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

// 효율적인 화폐 구성
public class DP_04 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] coins = new int[n];
        int[] d = new int[m + 1];

        // 화폐 입력
        for (int i = 0; i < n; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        // DP 테이블 초기화
        for (int i = 0; i < m + 1; i++) {
            d[i] = 10001;
        }

        // 점화식에 따라 반복문 실행
        d[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = coins[i]; j < m + 1; j++) {
                d[j] = Math.min(d[j], d[j - coins[i]] + 1);
            }
        }

        // 만들 수 없는 경우 -1 출력
        if (d[m] == 10001) {
            System.out.println(-1);
        } else {
            System.out.println(d[m]);
        }
    }
}

📄 해설

  • 점화식 유도 못해서 해설 보고 풀이하였음
  • 나중에 다시 풀어보면서 점화식 직접 유도해봐야함
profile
조금 느릴게요~

0개의 댓글