[ 백준 25496번 ] 장신구 명장 임스

1. 문제

25496번: 장신구 명장 임스

 

2. 풀이

욕심쟁이 알고리즘(Greedy Algorithm)을 통해서 풀이할 수 있는 문제로, 남아 있는 피로도를 어떻게 하면 가장 효과적으로 사용할 수 있을 것인가를 해결하는 것이다.

 

장신구를 제작하는데 드는 피로도가 작은 것을 최대한 먼저 제작한다면, 다른 장신구를 제작할 수 있는 문제로 분할할 수 있다. 따라서 입력받은 피로도를 작은 순서로 정렬하여, 순차적으로 카운트해주면 끝!

 

중요한 것은 피로도가 190인 상황에서 12의 피로도가 필요한 장신구를 제작할 수 있다는 점이다. 따라서 장신구를 제작할 때, 남은 피로도보다 소모되는 피로도가 작거나 같은 조건을 추가해서는 안된다.

 

3. 소스코드

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int P = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        while (N-- > 0) {
            pq.add(Integer.parseInt(st.nextToken()));
        }

        int left = 200 - P;
        int cnt = 0;
        while (left > 0 && !pq.isEmpty()) {
            left -= pq.poll();
            cnt++;
        }

        bw.write(cnt + "");
        bw.close();
        br.close();
    }

}