[백준]2294번. 동전2(JAVA)

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

---

문제

---

풀이

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

public class Main {

    public static void main(String[] args) throws Exception{
        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());
        int[] arr=new int[n+1];

        for(int i=1;i<=n;i++)
        {
            st=new StringTokenizer(br.readLine());
            arr[i]=Integer.parseInt(st.nextToken());
        }

        int[] dp=new int[k+1];
        Arrays.fill(dp,10001);
        dp[0]=0;

        for(int i=1;i<=n;i++){
            for(int j=arr[i];j<=k;j++){
                dp[j]=Math.min(dp[j],dp[j-arr[i]]+1);
            }
        }

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

}

 

dp를 이용한 풀이이다. 처음엔 동전의 값으로 나눠 (몫 + 나머지에 대한 dp)를 이용하는 방식을 사용하려고 했다.

하지만 문제가 발생했고 이에 대한 반례는 다음과 같았다.

2 10

2

3 이라는 입력에 대해

금액:1 동전개수:10001
금액:2 동전개수:1
금액:3 동전개수:1
금액:4 동전개수:2
금액:5 동전개수:2
금액:6 동전개수:2
금액:7 동전개수:10001
금액:8 동전개수:3
금액:9 동전개수:3
금액:10 동전개수:5 <<<< 과 같은 오류가 나오게 된다.

분명 2와 3이라는 동전으로 7도 만들 수 있고, 10은 4개면 만들 수 있다. 그럼 왜 이런 오류가 발생했나 생각해보면 케이스에 대한 세심한 검토없이 dp를 무작정 도입하려고 한 것 같다.

 

알고리즘을 여러가지 알고 떠올릴 수 있는 것은 발전하고 있지만 떠올린 이후에 더욱 정확히 적용시키는 연습을 해야 실수없고 빠르고 정확하게 문제를 해결할 수 있을 것 같다.