[Beakjoon] 2294 동전 2 (Java)

문제 링크

BOJ 2294 : 동전 2

문제

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

풀이

주어진 n개의 동전을 이용해 k를 만들어야 한다.

단순하게 생각하면 가장 큰 값의 동전부터 사용할 수 있는 만큼 최대로 사용하면 되지 않을까 라는 생각이 들지만, 이 모든 경우에서 k값을 만들 수 있을 때만 사용 가능하다.

예를 들어

3 15
2
5
12

위와 같은 입력이 주어질 때, 12원을 사용해버리면 나머지 동전들로 k를 만들 수 없다.

3 15
1
5
12

문제에서 주어진 예시를 봤을 때도 12원을 사용한 후 1원으로 3을 만들면 총 4개의 동전을 사용한다.
이는 최소값이 아니다.

발생 가능한 상황이 잘 예측이 안되어 모든 상황을 확인해 봐야 하는 상황이다.
다이나믹 프로그래밍 유형에서 자주 등장하는 경우인 것 같다.

N의 최대 값이 100이므로 충분히 시도해볼만 하다.

dp배열의 각 인덱스에 저장되는 값은 해당 인덱스 값을 만드는데 드는 최소 개수의 동전이다.

동전 c를 한개 사용하여 k를 만드는 최소 동전 개수는
dp[k-c] + 1 이다.

점화식은 다음과 같다.

점화식

  dp[i] = Math.min(dp[i], dp[i - coin] + 1);

코드

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n, k;
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        ArrayList<Integer> coins = new ArrayList<Integer>();
        for(int i=0; i<n; i++){
            int a = Integer.parseInt(br.readLine());
            coins.add(a);
        }


        int[] dp = new int[k+1];
        Arrays.fill(dp, 101010);
        dp[0] = 0;
        for(int i=0; i<=k; i++){
            for (int coin : coins) {
                if (i - coin >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        if(dp[k] != 101010) System.out.println(dp[k]);
        else System.out.println(-1);
    }

}

주의할 점은 dp를 INTAGER.MAX를 이용해 초기화하면 점화식에서 overflow가 발생하여 정상적으로 작동하지 않는다.
따라서 적당히 큰 값으로 dp 배열을 초기화해줘야 한다.