백준 11047번 동전 0

동전 0는 주어진 동전(동전의 종류는 N개이다)을 활용해 최소한의 개수로 거스름돈(K)을 지불하는 문제다.

 

먼저, 내가 사용할 수 있는 동전의 종류를 기억하자

int[] coins = new int[N];

for (int i = 0; i < N; i++) {
	coins[i] = in.nextInt(); // coins = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
}

 

최소한의 개수로 동전을 사용해 거스름돈을 지불하기 위해서는 기억했던 동전의 종류(coins) 중 값어치가 높은 동전부터 최대한 활용해야 한다.

for (int i = N-1; i >= 0; i--) {
	int coin = coins[i]
}

 

그러나 4,200원의 거스름돈을 지불하기 위해 10,000원짜리 동전을 사용하지는 않는다. 따라서, 거스름돈의 크기와 현재 내가 활용하고자 하는 동전의 크기를 비교한다.

for (int i = N-1; i >= 0; i--) {
	int coin = coins[i]
    
    if (coin > K) {
    	continue;
    }
}

 

거스름돈 지불에 활용할 수 있는 적절한 값어치의 동전을 손에 쥐었다면 지불을 시작하자.

4200원을 지불하는데, 1000원짜리 동전을 쥐었다고 가정한다면 4개의 동전이 필요할 것이다.

1000원짜리 동전을 활용하여 4200원 중 4000원을 지불하였다면 거스름돈을 수정한다.

ncoin = K / coin; // 동전의 개수 : 거스름돈 나누기 동전의 몫
K %= coin // 거스름돈 잔액 : 거스름돈 나누기 동전의 나머지

 

위의 흐름에 따라 완성된 코드는 다음과 같다.

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int N = in.nextInt();
        int K = in.nextInt();

        int[] coins = new int[N];
        for (int i = 0; i < N; i++) {
            coins[N - i - 1] = in.nextInt();
        }

        int cnt = 0;
        for (int coin : coins) {
            if (coin > K) {
                continue;
            }

            cnt += K / coin;
            K %= coin;
        }
        System.out.println(cnt);
    }
}