[JAVA] 백준 알고리즘 2294번 문제 풀이 (동전2)

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

2294번: 동전 2

 

 

소스코드

import java.util.Scanner;

public class Sanizzang {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        int[] count = new int[k + 1];
        for (int i = 0; i < k + 1; i++) {
            count[i] = 100001;
        }
        count[0] = 0;

        int[] coin = new int[n];
        for (int i = 0; i < n; i++) {
            coin[i] = sc.nextInt();
        }

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

        System.out.println(count[k] == 100001 ? -1 : count[k]);
        sc.close();
    }
}

 

소스설명

1. 사용한 동전의 최소 개수를 저장하기위한 count 배열 생성

2. 동전의 최소가치인 100,000보다 1 높은 100,001를 count배열에 대입(사용한 동전의 개수가 최악일 경우 100,000개이기 때문)

3. coin배열에 있는 각각의 동전의 가치값들을 시행하기 위해 n번의 loop를 돌리고

4. 그 안에는 동전의 가치값부터 k까지의 최소 동전의 최소 사용 갯수만큼 카운트해준다.

5. 만약 최종적으로 count[k]의 값에 100001값이 들어있다면 입력된 동전의 가치로는 k원이 되지 못하므로 -1을 출력하고 그렇지 않으면 count[k]의 값을 출력하도록한다.