BOJ#2294 동전 2

BOJ#2294 동전 2

* 문제

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

* 풀이

dp 기본 문제입니다.

solve 함수는 크게 3부분으로 구성되어 있습니다.

dp 정의

dp[coinSum] : 현재 동전의 합이 coinSum일 때, k가 되기 위해 추가해야 하는 동전의 최소 개수

solve(coinSum) 함수 : dp[coinSum]을 반환하는 함수.

1. 기저 사례

동전의 합이 k에 딱 맞는 경우, return 0

동전의 합이 k에 맞지 않는 경우, return 매우 큰 수

        if (coinSum == k) return 0;
        if (coinSum > k) return INF;

2. 메모이제이션

dp 배열의 값을 -1로 초기화 했습니다. 즉, dp[coinSum]이 -1인 경우 메모이제이션 대상이 아닙니다.

        if (dp[coinSum] != -1) return dp[coinSum];

3. 탐색

dp 배열 정의에 따라 초기값을 매우 큰 수인 INF 설정합니다.

이후 주어진 동전 배열에 따라 탐색을 시도하고, 그 중 최소값을 dp[coinSum]에 저장하여 반환합니다.

        dp[coinSum] = INF;

        for (int i = 0; i < n; i++) {

            dp[coinSum] = Math.min(dp[coinSum], solve(coinSum + coin[i]) + 1);
        }

        return dp[coinSum];

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%232294/src/Main.java

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 n;
    static int k;
    static int[] coin = new int[101];
    static int[] dp = new int[10001];

    static final int INF = 100000000;

    static {

        Arrays.fill(dp, -1);
    }

    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());

        for (int i = 0; i < n; i++) coin[i] = Integer.parseInt(br.readLine());

        int ret = solve(0);
        System.out.println(ret == INF ? -1 : ret);
    }

    static int solve(int coinSum) {

        if (coinSum == k) return 0;
        if (coinSum > k) return INF;

        if (dp[coinSum] != -1) return dp[coinSum];

        dp[coinSum] = INF;

        for (int i = 0; i < n; i++) {

            dp[coinSum] = Math.min(dp[coinSum], solve(coinSum + coin[i]) + 1);
        }

        return dp[coinSum];
    }
}