[백준] 2294번 동전 2

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   n가지 종류의 동전을 적당히 사용하여 그 차이의 합이 k원이 되도록할 때, 동전의 개수가 최소인 경우를 구하는 문제이다. 각 동전의 개수는 제한없이 사용 가능하며, 사용한 동전의 구성이 같으면, 사용한 순서에 대한 차이를 구분하지 않는다.

   첫째줄에 n, k가 주어지고, 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. (가치가 같은 동전이 여러 번 주어질 수 있다.) 제한 사항은 다음과 같다.

 

• 1 ≤ n ≤ 100
• 1 ≤ k ≤ 10,000
• 1 ≤ 동전의 가치 ≤ 100,000
• k를 만들 수 없는 경우 -1을 출력한다.

 

 

---

접근 방식

   DP의 개념을 이용해 문제를 해결하였다. DP 과정에서 저장될 값은 현재 가치를 만들 수 있는 동전의 최소 개수이다. 예제를 통해 해결 과정을 알아보자.

 

 

   가치가 1인 코인 한 종류만 있고, k가 7일 때 동전의 최소 개수를 구해보자. 먼저 가치가 0인 경우는 만들 수 없기 때문에 0으로 초기화된 것이 마땅하다. 다음은 가치가 1인 경우를 보자. 가치가 1인 코인을 가지고 가치가 1인 경우를 만들 때 코인의 최소 개수는 몇 개일까? 당연히 가치가 1인 코인 하나를 사용해서 만들 수 있기에 1개일 것이다.

 

 

   나머지 가치에 대해서도 진행해보면 다음과 같이 나올 것이다.

 

 

   그렇다면 가치가 2인 코인 한 종류만 있는 경우에 대해서 진행해보자.

 

 

   가치가 2인 코인으로는 가치 0과 1을 만들 수 없다. 따라서 가치가 2인 경우부터 만들 수 있다.

 

 

   3인 경우는 가치가 2인 코인으로 만들 수 없다. 나머지 부분에 대해서도 진행해보자. 가치가 2인 코인만 있는 경우 구하고자하는 가치가 7일 때의 최소 코인의 개수를 구할 수 없다. 이 경우는 문제의 조건에 의해 -1이 출력될 것이다.

 

 

   이번엔 가치가 3인 코인이 있는 경우에도 진행해보자. 코인의 가치가 3인 경우 가치가 0, 1, 2인 경우는 만들 수 없다. 지금까지의 과정을 확인해보면 항상 코인의 가치와 동일한 인덱스(가치)부터 초기화가 발생하는 것을 알 수 있다.

 

 

   이번엔 가치가 1, 2, 3인 코인이 있을 때를 알아보자. 이전에 만들었던 배열들을 이용해서 우선 가치가 1, 2인 코인들에 대해 값을 구해보자.

 

 

   가치가 0인 경우는 항상 만들 수가 없다. 가치가 1인 경우는 코인의 가치가 1인 코인으로만 만들 수 있다.

 

 

   가치가 2인 경우는 어떨까? 가치가 1인 경우와 2인 경우 모두 만들 수 있다. 하지만 코인의 개수가 더 작은 것은 가치가 2인 코인을 한 개 사용하여 만든 경우이다. 즉, 가치가 1인 코인과 2인 코인으로 만들 수 있는 경우 중에서 더 작은 값으로 초기화한다.

 

 

   가치가 3인 경우는 가치가 1인 경우의 코인으론 만들 수 있지만 2인 경우로는 만들 수 없었다. 하지만 두 코인을 섞어서 만들 수 있는 경우가 생겼다. 즉, 코인이 2개 이상인 경우부턴 현재 가치를 만드는 경우에 대해 다른 시점으로 접근할 수 있게 된다. 지금과 같은 경우에는 '가치가 2인 코인을 더하여 현재의 가치인 3을 만드는 경우가 존재하는가?'이다. 2를 더해 가치가 3이 되는 경우는 가치가 1인 경우이다. 따라서 가치가 1인 경우에서의 코인의 최소 개수에 1개를 더한(가치가 2인 코인을 한 개 더한 것) 경우를 고려하여 사용된 코인의 최소 개수를 초기화해야 한다. (1을 더해 가치가 3이 되는 경우는 가치가 2인 경우는 가치가 1인 코인만 있는 경우에서 바로 구할 수 있다.)

 

 

   가치가 4인 경우는 가치가 1인 코인을 더해 만드는 경우, 가치가 2인 코인을 더해 만드는 경우 등을 고려하여 구할 수 있다. 같은 방법으로 나머지 부분도 초기화해보자.

 

 

   새로 만들어진 배열의 의미하는 것은 가치가 1, 2인 코인들을 이용해 각 가치를 만들 수 있는 코인의 최소 개수이다. 만들어진 배열과 가치가 3인 코인이 추가된 경우에 대해 배열을 초기화해보자.

 

 

   가치가 1, 2인 경우는 그 값이 그대로 초기화된다. 하지만 가치가 3인 경우는 각각 가치가 1, 2, 3인 코인을 더해 만들어지는 경우를 고려하여 그 중 가장 작은 값을 구해야 한다. 지금은 고려할 코인의 수가 적어 크게 상관없지만 코인이 많아질수록 매번 고려한다면 복잡해질 것이다. 여기서 우리는 이전에 만들었던 배열의 의미를 생각해보아야 한다. 위 그림에서의 첫번째 배열의 각 칸의 의미는 '가치가 1, 2인 코인들을 이용해 각 가치를 만들 수 있는 코인의 최소 개수이다.' 따라서 우리는 모든 경우를 고려할 필요없이 인덱스 3번의 값과 가치가 3인 코인을 더해 가치가 3이 되는 경우만을 고려하면 된다.

 

 

   나머지를 초기화해 나가면 결국 다음과 같은 식을 얻을 수 있다.

 

현재 가치를 만드는 최소 코인 개수 = Math.min('현재 가치 - 현재 코인의 가치'를 만드는 코인 개수 + 1, 이전 코인들로 현재 가치를 만드는 최소 코인 개수)

 

   이전 코인들로 찾은 최소의 개수는 전부 기억할 필요없이, 현재 코인과 이전 코인들 이렇게 두 가지로 구분하면 된다. 즉, 이전까지의 코인들로 찾은 누적된 경우가 필요하기 때문에 DP를 1차원 배열 형태로 만들 수 있으며 다음 식을 도출할 수 있다.

 

dp[value] = Math.min(dp[value - coinValue] + 1, dp[value])

 

※ 만들 수 없는 경우는 0으로 초기화된 상태로 위와 같은 점화식을 수행하게 되는 경우 0이 최소값으로 인식되어 의도하지 않은 결과가 나오게 된다. 따라서 dp의 초기값은 나올 수 있는 최대값 + 1의 형태를 취하자. (단, 0번째 인덱스는 0으로 초기화하는 것이 옳다.)

---

코드

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

public class 백준2294번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer token;

    public static void main(String[] args) throws IOException {
        token = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(token.nextToken());
        int K = Integer.parseInt(token.nextToken());
        int[] coin = new int[N];
        //각 가치를 만들 수 있는 동전의 최소 개수 저장
        int[] dp = new int[K + 1];

        //가치를 만들 수 있는 동전의 최대 개수 + 1개로 초기화
        Arrays.fill(dp, 10001);
        //0번째는 동전을 사용하지 않은 경우이기 때문에 항상 0으로 초기화
        dp[0] = 0;
        for (int i = 0; i < N; i++)
            coin[i] = Integer.parseInt(br.readLine());

        //동전의 종류만큼 진행
        for (int i = 0; i < N; i++) {
            //현재 동전의 가치
            int coinValue = coin[i];
            //동전의 가치부터 K까지 dp 진행
            for (int value = coinValue; value <= K; value++)
                //현재 가치를 만들 수 있는 동전의 최소 개수는 다음 두 가지 경우 중 최소를 취함
                //현재 동전의 가치를 더해서 현재 가치가 만들어진 경우
                //이전 과정에서 만들었던 현재 가치
                dp[value] = Math.min(dp[value - coinValue] + 1, dp[value]);
        }

        //K번째 값이 변경된 경우 현재 가진 동전의 종류들로 만들 수 있음
        System.out.println(dp[K] == 10001 ? -1 : dp[K]);
    }
}