[BOJ2294] 동전 2

문제 유형

동적 계획법 (Dynamic Programming), 메모이제이션 (Memoization)

문제 링크

https://www.acmicpc.net/problem/2294

풀이

0. 문제 해석

n가지 종류의 동전이 주어질 때, 이 동전들을 사용해 가치의 합이 k원이 되도록 만들어야 한다. 이때 사용되는 동전 개수의 최솟값을 찾는 문제다. 만약 목표 금액 k원을 만드는 것이 불가능하다면 -1을 출력해야 한다.

1. 접근 방법

주어진 동전들로 특정 금액을 만드는 최소 동전 개수를 구하는 것은 동적 계획법(Dynamic Programming)의 전형적인 활용 사례다. 목표 금액 k를 만들기 위한 최소 동전의 개수는, k에서 사용 가능한 각 동전의 가치를 뺀 금액(k-coin)을 만드는 데 필요한 최소 동전 개수와 직접적인 연관이 있다.

예를 들어, k원을 만들기 위한 최소 동전 개수는 (k - coin_1)원을 만드는 최소 개수 + 1, (k - coin_2)원을 만드는 최소 개수 + 1, ... 중에서 가장 작은 값이 된다. 이러한 점화식을 재귀 호출로 풀 수 있지만, 동일한 금액에 대한 계산이 반복적으로 일어나는 비효율이 발생한다. 이 문제를 해결하기 위해, 한 번 계산된 결과는 저장해두고 다시 사용하는 메모이제이션(Memoization) 기법을 적용하여 중복 계산을 제거한다.

2. 아이디어

• dp[i]를 '금액 i를 만드는 데 필요한 최소 동전의 개수'로 정의한다.
• 최종적으로 구하려는 답은 dp[k]가 된다.
• dp 배열을 특정 값(-1)으로 초기화하여 해당 금액에 대한 계산이 이미 수행되었는지 여부를 판별한다.
• dp[0]은 0원을 만드는 경우로, 0개의 동전이 필요하므로 dp[0] = 0으로 설정한다.
• 재귀 함수 dfs(x)는 금액 x를 만드는 데 필요한 최소 동전 개수를 반환하도록 설계한다.
• 함수 내부에서는 모든 동전 c에 대해 dfs(x - c) + 1을 시도하고, 이들 중 가장 작은 값을 찾아 dp[x]에 저장한다.
• 만약 특정 금액을 만드는 것이 불가능하다면, 아주 큰 값(코드에서는 100001)을 반환하여 만들 수 있는 경우와 구분한다.

3. 동작 방식

코드는 다음 순서로 동작한다.

1. main 함수에서 N(동전 종류 수)과 target(목표 금액)을 입력받는다.
2. dp 배열을 target + 1 크기로 생성하고, 아직 계산되지 않았음을 의미하는 -1로 모두 채운다. dp[0]은 0으로 설정한다.
3. dfs(target)를 호출하여 목표 금액을 만드는 데 필요한 최소 동전 개수 계산을 시작한다.
4. dfs(x) 함수는 다음과 같이 동작한다.
   • 만약 x가 0이면, 0을 반환한다. (기저 조건)
   • 만약 x가 음수이면, 만들 수 없는 경우이므로 IMPOSSIBLE 값을 반환한다. (예외 처리)
   • 만약 dp[x]가 -1이 아니라면, 이미 계산된 값이므로 dp[x]를 즉시 반환한다. (메모이제이션)
   • minCnt 변수를 IMPOSSIBLE로 초기화한다.
   • 사용 가능한 모든 동전 coin에 대해 반복한다.
   • dfs(x - coin)을 재귀적으로 호출하여 x - coin 금액을 만드는 최소 개수를 얻는다.
   • 만약 반환된 값이 IMPOSSIBLE이 아니라면, minCnt를 min(minCnt, 반환된 값 + 1)로 갱신한다.
   • 모든 동전에 대한 반복이 끝나면, 계산된 minCnt 값을 dp[x]에 저장하고 반환한다.
5. 최종적으로 main 함수에서 dfs(target)의 반환 값을 확인한다. 만약 IMPOSSIBLE이라면 -1을, 아니라면 해당 값을 출력한다.

4. 코드

package BOJ2294;

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[] dp;
    static int[] coins;
    static int target, N;
    static final int IMPOSSIBLE = 100001;

    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());
        target = Integer.parseInt(st.nextToken());
        coins = new int[N];
        //특정 금액을 만드는 데 필요한 최소 동전 개수
        dp = new int[target + 1];
        Arrays.sort(coins);
        for (int i = 0; i < N; i++) {
            coins[i] = Integer.parseInt(br.readLine());
        }
        Arrays.fill(dp, -1);
        dp[0] = 0;
        int result = dfs(target);
        if (result == IMPOSSIBLE) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }

    }

    public static int dfs(int x) {
        if (x == 0) {
            return 0;
        }
        if (x < 0) {
            return IMPOSSIBLE;
        }
        if (dp[x] != -1) {
            return dp[x];
        }
        int minCnt = IMPOSSIBLE;
        for (int coin : coins) {
            int subResult = dfs(x - coin);
            if (subResult != IMPOSSIBLE) {
                minCnt = Math.min(minCnt, subResult + 1);
            }
        }
        return dp[x] = minCnt;
    }
}```