[백준] 2294번 동전 2

생각

금액이 다른 동전 N개와 원하는 금액 K가 주어진다. N개의 동전들을 최소한으로 사용하여 K를 만들 때 그 최소한의 동전수를 출력하여라. 만들 수 없을 경우 -1을 출력한다.

처음 생각

DFS를 통해 풀이를 하였으나 시간 초과가 나왔다.

다음 생각

이런 동전류의 문제는 이전 값을 계산해서 나아가는 다이나믹 프로그래밍(DP) 방식을 사용해서 푸는 경우가 많으므로 DP로 접근하였다.

다다음 생각

동전의 숫자를 구하는 것이므로 이 금액을 만들 수 있나의 개수를 파악하면서 가는것이 아닌 이 금액을 몇 개의 동전으로 만들 수 있나를 파악하면서 가도록 진행하였다.

자세한 설명은 코드상에 주석으로 달아 놓았습니다.

다다다음 생각

따라서 DP를 구하기에 앞서 DP에 해당 Index 1~K 일 때, 주어진 동전의 배수를 미리 채워넣었다.

다다다다음 생각

해당 금액 index 에서 사용할 수 있는 동전을 뺀 index의 값이 0이 아니라면 그 dp값 +1 만큼 의 동전 개수로 해당 금액이 만들어 질 수 있으므로 1원 부터 진행을 해나갔다.

다다다다다음 생각

맞는것 같은데 1시간 이상 틀렸습니다를 봤고, 결론은 if문 처리에서 break가 아닌 continue를 해주어 다른 동전 금액들의 경우에도 살펴봐야 했었다.

방안

1) break 를 continue 로 바꾸어 모든 동전 조건을 탐색하도록 하였다.

2) 위의 방식은 오름차순이 만족되어 있어야지 작은 금액의 동전부터 판단이 가능하다. 문제 조건에 오름차순으로 주어진단 말이 없으므로 배열을 정렬 시켰다.

3) DP 너무 어렵습니다~

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,k;
    static int[] coin,dp;
    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()); // 원하는 값
        coin = new int[n];
        dp = new int[k+1];
        for(int i=0;i<n;i++)
            coin[i] = Integer.parseInt(br.readLine());
        Arrays.sort(coin);
        solve();
        System.out.println(dp[k]==0?-1:dp[k]);
    }
    
    private static void solve() {
        // 해당 숫자를 몇 개의 동전으로 만들 수 있나
        // 예제에 해당하는 1인 경우 1~k(15)까지 1,2,3,4...15가 들어간다.
        // 오름 차순으로 들어가니 큰 동전은 알아서 적게 사용된게 들어간다.
        // 예제에 해당하는 5인 경우 5,10,15에 1,2,3이 들어간다.
        for(int i=0;i<n;i++) {
            for(int j=1;coin[i]*j<=k;j++) {
                dp[j*coin[i]]=j;
            }
        }
        
        // 1부터 k 금액까지 살펴본다.
        // 해당 금액(i)에서 사용할 수 있는 동전 금액을 뺀 dp 배열에서 +1을 해주면
        // 해당 금액을 만들 수 있는 동전 수가 된다.
        // 예제로 3을 만든다하면 dp[3]에는 3이 있을 것이다.
        // 3-1(금액1) = 2, dp[2]에는 2가 있을 것이다. +1 해주어 dp[3]에는 다시 3이 저장된다.
        // 3-5(금액2) 는 마이너스 값이므로 if문에 걸려서 반복문이 종료된다
        // (동전이 오름차순 정렬 되어있으므로 한 번 마이너스 값이 나오면 다 마이너스가 나올 것이기 때문에)
        // 다시 예제로 5를 만든다하면 dp[5]에는 1이 있을 것이다.
        // 5-1(금액1) = 4, dp[4]에는 4가 있을 것이다. 최소로 동전을 사용해야 하므로
        // 조건 문을 통해 현재 바꾸고자 하는 dp[5]의 값이 뺴서 계산한 dp[4]+1 보다 작다면 갱신하지 않는다.
        // dp[5] < dp[4]+1 이기 때문에 갱신되지 않는다.
        // => 1 < 4+1
        // => if(dp[i]<dp[i-coin[j]]+1;
        // 이런식으로 계속 계산을 해나간다.
        // dp[i-동전금액] == 0 일 경우 이전 금액을 못 만든다는 것이므로 dp[i]도 만들 수 없으므로
        // 다음 동전 케이스를 살펴보러 넘어간다.
        // dp[i]가 클경우만 집어넣게 되면 위에서는 잡히지 않은
        // 예를들어 2 3 이 있을 경우 처음 넣어주는 값에서 5는 값이 0일 것이다.
        // 따라서 dp[i]가 클 경우 뿐만아니라 ==0 일 경우도 처리해주었다.
        for(int i=1;i<=k;i++) {
            for(int j=0;j<n;j++) {
                if(i-coin[j]<0) break;
                if(dp[i-coin[j]]==0) continue;
                if(dp[i] > dp[i-coin[j]]+1)
                    dp[i] = dp[i-coin[j]]+1;
                else if(dp[i]==0)
                    dp[i] = dp[i-coin[j]]+1;
            }
        }
//        for(int i=0;i<=k;i++)
//            System.out.println(i+"는 ::: "+dp[i]);
//        System.out.println("----------------");
    }
}