[백준] 11047 동전 0 - Java

문제 - 동전 0

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

 

 

 

접근 방법

 

이 문제는 그리디로 풀 수 있다

주어진 동전을 최소로 하여 K를 만들려고 한다 

그럼 제일 큰 동전 부터 해서 K가 되게 만들면 될 것 같다

동전 목록들을 자료구조에 넣고 내림 차순으로 정렬 해서 풀면 될 것 같다

 

나는 자료구조를 우선순위 큐를 사용했는데 (요즘 우선순위 큐에 맛들렸다)
사용한 이유는 

우선순위 큐까지 사용해서 풀 문제는 아니지만 만약 배열이나 list를 사용하면 내림차순으로 정렬을 해줘야 한다

 

하지만 우선순위큐를 사용하면 큐에서 데이터를 뺄때 정렬이 된 상태로 데이터가 출력이 되기 때문이다

---

코드 작성(우선순위 큐를 사용했을때)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        try (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());

            Queue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());

            for (int i = 0; i < N; i++) {
                queue.add(Integer.parseInt(br.readLine()));
            }

            int count = 0;
            while (!queue.isEmpty()) {
                int money = queue.poll();
                if (K >= money) {
                    int a = K / money;
                    K -= (money * a);
                    count += a;
                }
            }

            System.out.println(count);
        }
    }
}

 

 

코드 작성 (리스트를 사용했을때)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        try (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.sort(Comparator.reverseOrder());
            int count = 0;

            for(int money : list){
                if (K >= money) {
                    int a = K / money;
                    K -= (money * a);
                    count += a;
                }
            }

            System.out.println(count);
        }
    }
}