[Java] 백준 2294 동전 2

문제

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

 

입력

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

 

출력

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

 

문제 링크 : 동전 2

---

설명

얼마 전 푼 동전 1과 비슷한 문제라서 점화식도 사실 어렵지 않게 세웠다.

그래서 호기롭게 제출을 했으나... 84% 에서 틀렸습니다 를 보고 엥? 했던...

 

그래서 처음에 제출했던 코드

    import java.io.*;
    import java.util.*;

    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 = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            long[] dp = new long[k + 1];
            boolean[] visited = new boolean[n + 1];
            for (int i = 1; i <= k; i++){
                dp[i] = i;
            }

            for (int i = 1; i <= n; i++) {
                int num = Integer.parseInt(br.readLine());
                for (int j = num; j <= k; j++){
                    visited[i] = true;
                    dp[j] = Math.min(dp[j], dp[j - num] + 1);
                }
            }
            boolean isFalse = false;
            for (int i = 1; i <= n; i++) if (visited[i]) {
                isFalse = true;
                break;
            }

            System.out.println((isFalse) ? dp[k] : -1);
        }
    }

 

틀렸습니다 를 받았기 때문에 더 자세하게 코드를 보았다.

 

내가 세운 점화식은 이러하였다.

예제 1번인데 15까지 한칸에 넣기에는 화면이 너무 작아지는 것 같아서 나눠서 작성했다.

 

동전의 최소 개수를 찾아야하기 때문에 1부터 k까지 가는 동안 주어진 동전을 몇개 사용하여 완성할 수 있는지를 계산해보았다.

 

맨 처음 주어진 동전이 1이기 때문에 1원의 동전으로 1부터 k(15)원까지 1원의 동전 사용 개수를 세준다.

다음으로 주어진 동전(5)으로 5원부터 k(15)원까지 앞의 동전 개수와 ,5원의 동전 사용 개수 중 더 최솟값으로 세준다.

다음으로 주어진 동전(12)으로 12원부터 k(15)원까지 앞의 동전 개수와 , 12원의 동전 사용 개수 중 더 최솟값으로 세준다.

 

따라서 점화식을 코드로 표현하자면 dp[j] = Math.max(dp[j], dp[j - num] + 1) 이 되겠다.

 

처음코드를 다시보면서 아 처음에 1~k를 무작정 넣은게 틀렸나 싶어서 dp[0] 초기값 빼고 다 Integer.MAXVALUE로 채워서 다시 제출했는데 또 틀렸습니다 가 떠서 뭐지뭐지 했는데 결국 문제는 -1 처리부분이였다...

 

코드

import java.io.*;
import java.util.*;

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 = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        long[] dp = new long[100001];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            int num = Integer.parseInt(br.readLine());
            for (int j = num; j <= k; j++){
                dp[j] = Math.min(dp[j], dp[j - num] + 1);	// 현재 값과 j-num + 1 한 값중 최솟값
            }
        }

        System.out.println((dp[k] == Integer.MAX_VALUE) ? -1 : dp[k]);
    }
}