[BAEKJOON] 2294. 동전2(Java)

:D 문제

---

문제

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

Baekjoon

2294번: 동전 2

 

 

:D 풀이 방법

---

이 문제는 DP로 접근해서 해결하였다.

먼저, 1부터 K까지의 가치의 합을 저장하기 위해 dp 배열을 만들어주었다. 현재 가지고 있는 동전으로 만들 수 없는 경우를 고려해주어여하기 때문에 10001로 dp 배열을 초기화 해주었다. 그리고, DP[0] = 0이 되게 설정해주었다.(0원의 가치를 만들기 위해서는 동전이 0개 필요함으로)

 

예제와 같이 동전이 총 3개(1원, 5원, 12원)이고,  K=15인 경우 아래와 같이 최소 필요한 동전의 수를 찾아갈 수 있다.

먼저, 다음과 같이 dp배열을 초기화 한다.

 

첫번째 1원으로 K의 가치를 만들 때 필요한 동전의 수를 담는다. 이 때, dp[k]에 저장되어 있는 동전의 수보다 필요한 동전의 수가 작다면 해당 값을 갱신한다.

 

다음 5원으로 K까지 가치를 만들 때 필요한 동전의 수를 담는다. 위와 같이 더 작은 값일 경우 갱신한다.

 

마지막으로 12원으로 K까지 가치를 만들 때 필요한 동전의 수를 담는다. 그럼 최종적으로 다음과 같이 갱신할 수 있다.

따라서, 최소 3개의 동전으로 15원을 만들 수 있다.

 

:D 작성 코드

---

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

public class Main {

    static int[] coins;
    static int[] dp;
    static int N, K;

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

        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 동전 종류
        K = Integer.parseInt(st.nextToken()); // 목표 금액

        // 동전 저장
        coins = new int[K];
        for (int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        // dp 배열 생성
        dp = new int[K + 1];

        // dp 배열 초기 가치 저장
        Arrays.fill(dp, 10001);

        // 0원은 0개의 동적이 필요함으로 dp[0] = 0;
        dp[0] = 0;

        // 값 갱신
        // 동전 수만큼 반복
        for (int n = 0; n < N; n++) {
            updateDP(n);
        }

        // 출력
        System.out.println(dp[K] == 10001 ? -1 : dp[K]);
    }

    private static void updateDP(int n) {
        for (int money = coins[n]; money <= K; money++) {
            dp[money] = Math.min(dp[money], dp[money - coins[n]] + 1);
        }
    }
}