[JAVA] 백준 11047 - 동전 0

백준 11047 - 동전 0

문제

---

알고리즘 (접근방법)

K의 값 보다 큰 값의 동전을 배제하고 생각하였다.
4200이면 4200 보다 큰 5000부터 동전을 배제하고
5000 보다 작은 값으로 나누고, 나누고 난 나머지를 다시 나누는 작업을 반복하였다.

---

코드

import java.io.*;

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

        String line[] = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int k = Integer.parseInt(line[1]);
        int count = 0;
        int coin[] = new int[n];

        for(int i=0;i<n;i++) { //동전의 종류 입력
            coin[i] = Integer.parseInt(br.readLine());
        }

        for(int i=n-1;i>=0;i--) {
            if(coin[i] <= k) { //현재 동전의 가치가 k 보다 작아야 연산 가능
                count += (k/coin[i]);
                k = k%coin[i];
            }
        }
        System.out.println(count);
    }
}