[백준 - 11047] 동전 0 - Java

문제 설명

 

11047번: 동전 0

 

풀이 회고

해당 문제에서 요구하는 것은 오름차순으로 동전의 가치가 주어졌을 때 해당 동전들로 k원을 만드는데 필요한 동전 개수의 최솟값입니다. 이 문제는 그리디 알고리즘의 유형으로 정답을 구하기 위해서는 가장 가치가 큰 동전들을 토대로 k원을 구성해야합니다.

 

이때 입력 받은 동전의 가치들을 저장한 배열은 오름차순으로 정렬되어있으므로 배열의 끝 부분부터 k원을 나누면서 몫이 존재할 때(1 이상일 때) 결과값(result)에 더해주도록 합니다. k를 나누는 과정에서 k가 0이 될 수도 있는데, 이 경우에는 더 이상 나누는 것이 무의미하므로 for문을 종료시킵니다.

 

 

전체 소스 코드

import java.util.Scanner;

class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();

        Integer[] prices = new Integer[n];

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

        int result = 0;

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

        System.out.println(result);
    }
}

 

 

참고자료

• https://www.acmicpc.net/problem/11047