[백준] no11047: 동전0

문제

: K를 만들 수 있는 최소한의 동전 개수 구하기

1. 첫 줄

 N : 동전 종류 개수 

 K : 목표 금액

2. N개의 줄 : 각 동전의 종류 (오름차순)

 

문제 링크 : https://www.acmicpc.net/problem/11047

---

원리

대표적인 그릳(Greedy)알고리즘

---

풀이방법

1. 동전단위가 큰 수부터 차례로 K를 나눔

2. 몫은 count

3. 나머지는 K로 다시 지정

4. 모든 동전을 반복

---

나의 코드

1. ArrayList와 Stream을 사용한 동전 목록 [로컬 테스트는 성공이나, 백준에선 ArrayList를 인식 못함]

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());
    List<Integer> list = new ArrayList<>();

    for(int i=0; i<N ; i++) list.add(Integer.parseInt(br.readLine()));
    List<Integer> sortedList = list.stream().sorted(Comparator.reverseOrder()).toList();
    int count = 0;
    for(int i=0; i<sortedList.size(); i++) {
        if(sortedList.get(i)<=K) {
            count += K/sortedList.get(i);
            K %= sortedList.get(i);
        }
    }
    System.out.println(count);
}

 

2. Array 사용

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[] coin = new int[N];
    for(int i = 0; i < N; i++) coin[i] = Integer.parseInt(br.readLine());
    int count = 0;

    for(int i = N - 1; i >= 0; i--) {
        if(coin[i] <= K) {
            count += (K / coin[i]);
            K = K % coin[i];
        }
    }
    System.out.println(count);
}