[백준] 동전 0(그리디 알고리즘)

백준 온라인 저지 11047번 - 동전 0

지난 그리디 알고리즘 포스팅에서 공부한 것을 간단한 코딩 테스트 문제에 적용시켜 보았다.

Coin0.java

package com.example.Baekjoon;

/**
 * 동전 0
 * 그리디 알고리즘으로 풀이
 * int N -> 보유 동전 개수(배열 A의 길이)
 * int K -> 목표 금액
 * int[] A -> 동전 금액 배열
 */
public class Coin0 {
    public int getMinCoins(int N, int K, int[] A) {
        int coinCnt = 0;

        // 오름차순 정렬이니 제일 비싼 가격부터 순회
        for (int i = N - 1; i >= 0; i--) {
            // 배열 요소 중 목표 가격보다 바로 작거나 같은 가격이 나왔다면
            if (A[i] <= K) {
                // 코인 개수 증가
                coinCnt += K / A[i];
                // 남은 채울 금액 할당
                K = K % A[i];
            }
        }

        return coinCnt;
    }
}

Coin0Test.java

package com.example.Baekjoon;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class Coin0Test {
    @Test
    public void testCoin0() {

        Coin0 c = new Coin0();

        int[] coins = { 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000 };

        int result1 = c.getMinCoins(10, 4200, coins);
        int result2 = c.getMinCoins(10, 4790, coins);

        assertEquals(6, result1);
        assertEquals(12, result2);
    }
}