BOJ11047 동전 0

https://www.acmicpc.net/problem/11047 (opens new window)

준규가 가지고 있는 동전은 총 N 종류이고, 각각의 동전은 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구한다.

동전의 가치는 오름차순으로 정렬되어 제공된다.

제출 코드

입력 받은 동전의 가치를 활용하여 동전 개수의 최솟값을 구한다.

아래는 최종 제출 코드이다.

import java.util.Scanner;

public class BOJ11047 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 동전의 종류 n개
        int k = scanner.nextInt(); // 가치의 합
        int[] coins = new int[n]; // 동전의 가치

        for (int i = 0; i < n; i++) {
            coins[i] = scanner.nextInt();
        }

        int result = 0;
        for (int i = n - 1; i >= 0; i--) {
            result += k / coins[i];
            k = k % coins[i];
        }

        System.out.println(result);
    }
}

#algorithm #BOJ #그리디 알고리즘