백준 2294번 동전 2 java

이 문제는 다이나믹 프로그래밍을 이용하여 동전과 가치의 합이 주어질 때 동전의 개수가 최소가 될 때를 찾는
문제입니다. 

이 문제는 아래의 문제와 비슷한 풀이로 풀 수 있으니 아래의 문제를 보고 오시는 것을 추천드립니다.

백준 2293번 : 동전 1 java

저는 이 문제를 N개의 동전의 가치들을 배열에 저장한 후 1원을 만들 때의 동전의 수부터 N원을 만들 때의 동전의 수를
저장해가며 해결하였습니다.

예제 1번을 이용하여 문제를 해결하는 과정을 설명드리겠습니다.

cnt[i]는 동전의 개수가 가치 i일 때 최소 몇 개로 표현할 수 있는지를 나타내는 배열입니다.

우선 1의 가치를 가진 코인만들 이용하여 각각의 수를 나타낼 때 동전의 수가 몇 개가 필요한지 확인해보겠습니다.

1의 가치를 가진 동전만으로 각각의 수를 표현하려면 다음과 같은 수의 동전이 필요합니다.

이제 2의 가치를 가진 동전을 같이 이용하여 각각의 수를 나타내 보도록 하겠습니다.

cnt[i]를 채우는 점화식은 cnt[i] = Math.min(cnt[i], cnt[i - coin[j]] + 1)입니다.

여기서 i는 cnt의 각각의 인덱스를 의미하고 j는 코인이 들어있는 인덱스를 의미합니다.

예를 들어 3이 들어 있는 칸에서 동전 1과 2를 이용하여 동전의 갯수를 구하고자 할 때 2는 coin[1]이므로
cnt[3]과 cnt[3 - 2] + 1의 값을 비교하게 됩니다.

cnt에 들어 있던 값은 3이었으니 cnt[1] + 1의 값인 2보다 크므로 cnt[3]의 값은 2초 바뀌게 됩니다.

이 과정을 위의 배열에 반복해서 해보도록 하겠습니다.

 그럼 다음과 같은 그림이 됩니다.

이제 마지막 코인인 5까지 활용하여 동전의 개수가 최소가 될 때를 구해보도록 하겠습니다.

위의 그림이 완성이 됩니다.

따라서 15의 가치를 만들 때 가장 동전을 적게 쓰는 수는 cnt[15]인 3입니다.

이를 코드로 구현해보도록 하겠습니다.

---

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());

        int[] coin = new int[N];
        int[] cnt = new int[K+1];

        //전체 배열을 최댓값으로 초기화
        for(int i = 1; i<=K; i++)
            cnt[i] = 100_001;

        for(int i = 0; i<N; i++)
            coin[i] = Integer.parseInt(br.readLine());

        Arrays.sort(coin);

        for(int i = 0; i<N; i++) {
            for (int j = coin[0]; j <= K; j++) {
                if (j < coin[i])
                    continue;

                cnt[j] = Math.min(cnt[j], cnt[j-coin[i]] + 1);
            }
        }

        for(int i = 1; i<=K; i++)
            if(cnt[i]==100_001)
                cnt[i] = -1;

        System.out.println(cnt[K]);
    }
}

위와 같은 코드로 문제를 해결할 수 있습니다.