[백준] 11047번 - 동전 0 [Java]

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

 

[백준] 11047번 - 동전 0 [Java]

[백준] 11047번 - 동전 0 [Java]

---

1.  아이디어

 

필요한 동전이 최소가 되려면 가장 단위가 큰 동전부터 최대로 사용하는 걸 반복하면 된다.

---

2. 문제풀이

 

동전의 가치가 오름차순으로 주어지는데 나중에 개수를 셀 때 향상된 for문으로 계산하기 위해 내림차순이 되게 배열에 저장한다. 이후 배열을 순회하며 단위가 큰 동전을 최대한 사용하고 동전을 사용한만큼 남은 금액을 갱신해주는 과정을 반복하면 된다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int ans = 0;

        int[] divArr = new int[N];

        // 향상된 for문을 사용하려고 역순으로 저장
        for (int i = N - 1; i >= 0; i--) {
            divArr[i] = Integer.parseInt(br.readLine());
        }

        // 동전 개수 세고 잔액 갱신
        for (int div : divArr) {
            ans += K / div;
            K %= div;
        }

        System.out.println(ans);
    }
}

---

4. 후기