[백준] 2294 - 동전 2 (java)

2294번: 동전 2

---

 

문제

주어진 종류의 동전으로 목표금액 k 를 만드는 것이다. 이때 동전의 최소 수를 구한다.

( 위 예제에서는 5원짜리 동전 3개를 사용하여 15를 만들어서 답이 3 )

첫째 줄 첫번째 숫자 n 은 동전의 종류 k는 목표값이다.

아래에는 n개의 수는 각각의 동전 가치를 나타낸다. (같은 동전이 올 수 있음)

 

 

문제 풀이

n개의 코인을 입력받을때 해당 코인의 금액을 dp의 index로 하고 값을 1로했다.

dp[입력받은 코인의 값] = 1;

만약 1원짜리 동전과 4원짜리 동전이 들어오면?

위에서 입력한 정보를 사용하여 다음 만들 수 있는 코인들을 dp 배열에 채워나간다.

        for (int i = 2; i <= k; i++) {
            for (int j = 1; j < i; j++) {
                if(dp[j]==0 || dp[i-j]==0) continue;
                if(dp[i]==0){
                    dp[i] = dp[i-j] + dp[j];
                }else{
                    dp[i] = Math.min(dp[i-j] + dp[j], dp[i]);
                }
            }
        }

i 는 현재 채워야할 dp 인덱스, j는 i에 빼줘서 배열의 모든 값중 최소값을 구한다.

 

dp[i] = dp[i-j] + dp[i] 이때 dp[i] 이나 dp[i-j]는 0이되면 만들 수 없는 숫자이다

 

만약 dp[4] 을 구한다고 하면

dp[1] + dp[3] ,

dp[2] + dp[2]

dp[3] + dp[1]

이런 식으로 전체 경우를 비교한다

 

만약 dp[i]가 0이면 위에서 구한 수를 dp에 바로 넣고 ( 최소값에 0이 들어가는걸 방지하기 위해)

아니라면 dp[i]와 비교하여 최소값을 넣어준다.

 

목표금액까지 동전 수를 다 구했다면 dp[k]를 출력한다.

만약 dp[k]가 0이면 만들 수 없는 금액이므로 -1을 출력한다

 

 

주의할점

dp의 배열 크기를 잘 조절해야한다.

목표금액인 k값이나 k+1 크기로 dp를 만들었다면 index에러가 뜰 수 있다

왜냐하면 목표 금액보다 더 큰 돈이 주어진다고 생각해보자 ( 목표금액은 5원 동전의 값은 9원 )

금액 9원을 index로 사용해야하는데 dp배열에는 5원 까지밖에 담을 수 없어서

런타임 에러 조심...

---

// https://www.acmicpc.net/problem/2294
// 동전 2

import java.util.Scanner;

public class B2294 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] dp = new int[100001];
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            dp[a] = 1;
        }
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j < i; j++) {
                if(dp[j]==0 || dp[i-j]==0) continue;
                if(dp[i]==0){
                    dp[i] = dp[i-j] + dp[j];
                }else{
                    dp[i] = Math.min(dp[i-j] + dp[j], dp[i]);
                }
            }
        }
        if(dp[k]==0) System.out.println(-1);
        else System.out.println(dp[k]);
    }
}