BOJ(백준 온라인 저지) 11047번 with 자바[JAVA]

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

11047번: 동전 0

 

---

문제를 보면

첫 번째 줄에 동전 종류의 개수와 맞춰야 하는 돈의 가치를 받을 수 있고,

두 번째 줄부터 N 개의 줄로 각 동전의 가치를 받을 수 있습니다.

 

이때 동전의 가치는 오름차순으로 주어집니다.

 

우선 동전의 개수가 가장 적으려면

 

맞춰야 하는 돈(* K) 에 대해 나눠서 얻을 수 있는 몫이 0보다는 크지만 다른 동전들에 비해 몫이 가장 작은 동전이 가장 많아야합니다. 말이 어렵지만 예시를 들어 설명하자면

 

K = 4200 이라고 주어졌을 때

동전의 개수가 가장 작으려면

1000 원 동전의 개수가 가장 많아야 합니다.

 

1000 원 초과의 동전은 나눴을 때 몫이 0보다 작고,

1000 원 미만의 동전은 나눴을 때 몫이 1000 원으로 나눴을 때 얻을 수 있는 몫(* 4)보다 큽니다.

 

이렇게 해서 1000 원 4 개,

나머지 금액 200 원(* 4200 % 1000 의 결과)에 대해 같은 방식으로 반복하면

최소 동전 개수를 알 수 있습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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[] value = new int[N];

        for(int i=0; i<N; i++)
        {
            value[i] = Integer.parseInt(br.readLine());
        }

        int totalCount = 0;

        for(int i=N-1; i>=0; i--)
        {
            int price = value[i];
            if(K / price != 0)
            {
                totalCount += K / price;
                K %= price;
            }
        }

        System.out.println(totalCount);

    }

}

---

• 느낀 점

...