백준 2294번 - 동전2 (JAVA)

문제링크

 

 

문제

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

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

입력

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

출력

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

 

 

---

문제 풀이 과정

동전문제는 그리디 문제로 많이 알려져 있지만, 이 문제는 그리디로 접근 하면 해결이 불가한 문제이다.

그리디로 풀이가 가능 한 경우는 거스름돈 5의 배수이거나 각각의 동전이 서로의 배수, 약수일 때 가능 하다.

 

임의로 주어지는 동전에 대해서는 DP(다이나믹 프로그래밍) 방법으로 문제를 접근해야 한다.

 

DP 방식으로 문제를 풀기 위해서는 주어진 동전을 오름 차순으로 정렬 해야한다.

그 다음 DP 용 배열을 하나 선언하여 적당히 큰 수로 초기화 시켜 준다.

이때 Integer.MAX_VALUE 를 사용하지 않는 이유는 계산 과정에서 오버플로어가 발생 가능성이 있기 때문이다.

 

Arrays.sort(coins);

int[] arr = new int[target + 1];
Arrays.fill(arr, Integer.MAX_VALUE - 1);

 

동전 1로 15까지 만들 수 있는 경우는 아래와 같다.

동전 5와 1로 만들 수 있는 경우는 1 ~ 4 까지는 동전 1로만 만들 수 있고, 5일때는 동전 5 1개로 만들 수 있다.

동전 5와 1로 6을 만들기 위해서는 각각 한개씩 사용하면 되므로 2개가 필요하다.

 

 

동전 3개 모두를 사용하는 경우를 보면 11까지는 동전 5일때와 경우가 같고 12일때는 동전 12 한개로 만들 수 있으므로 1로 변경이 된다.

15를 만드는 경우일 때는 원래 값(arr[15] == 3) 과 arr[15 - 12] + 1 ( 3 + 1) 를 비교하면 원래 값이 더 작으므로 이 값이 최종 값이 된다.

 

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

 

전체 코드