[백준] 1781번 컵라면 (JAVA)

문제

- 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시함

- 이때 각 문제에 데드라인을 정함

- 동호가 받을 수 있는 최대 컵라면 수 구하기

 

해결방법

문제에 따른 정보를 Homework class 형태로 입력받고 데드라인을 기준으로 정렬하였고, 데드라인이 같다면 컵라면을 더 많이 주는 순으로 정렬할 수 있도록 구성하였다. 풀 문제가 정해지면 noodles 리스트에 저장해주었다. noodles 리스트는 컵라면을 더 많이 받기 위해서 정렬을 할 수 있었으면 좋겠다는 생각에 우선순위 큐를 사용하였다. 

input

2 100
2 100
3 500
3 500

이렇게 주어진다고 하면, (2, 100), (2, 100), (3, 500)을 선택하는 것 보다 (2, 100), (3, 500), (3, 500)을 선택해야 컵라면을 더 많이 받을 수 있다. 즉,  "데드라인이 작은 문제부터 해결해야 문제를 많이 풀 수 있음, 데드라인의 크기에 상관없이 더 많은 컵라면을 획득해야 함" 이 두 조건을 만족하기 위해서 위처럼 코드를 짜려고 했다.

참고 ) https://maivve.tistory.com/318

따라서, 우선순위 큐의 원소 개수(며칠째 진행 중인 것인지-데드라인과 관련)가 현재 판단하려고 하는 문제의 데드라인보다 작다면 바로 그 문제를 해결할 수 있도록 하였고, 우선순위 큐의 원소 개수가 데드라인보다 같다면 큐 안에 있는 컵라면 수를 확인하여 현재 판단하려고 하는 문제의 컵라면 수보다 작다면 현재 문제를 풀 수 있도록 하였다.

 

코드

import java.io.*;
import java.util.*;

// 문제 class
class Homework implements Comparable<Homework> {
    int no;
    int deadline;
    int noodle;

    public Homework(int no, int deadline, int noodle) {
        this.no = no;
        this.deadline = deadline;
        this.noodle = noodle;
    }
	
    // 데드라인을 기준으로 정렬(같다면 컵라면을 많이 주는 순으로 정렬)
    @Override
    public int compareTo(Homework o) {
        if(this.deadline == o.deadline) return o.noodle - this.noodle;
        return this.deadline - o.deadline;
    }
}

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int result = 0;
        List<Homework> homeworkList = new ArrayList<>();
        PriorityQueue<Integer> noodles = new PriorityQueue<>();		// 최종적으로 받을 수 있는 컵라면 수 저장 큐

        for(int i = 0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int deadline = Integer.parseInt(st.nextToken());
            int noodle = Integer.parseInt(st.nextToken());
            homeworkList.add(new Homework(i+1, deadline, noodle));
        }

        Collections.sort(homeworkList);

        for(int i = 0; i<N; i++) {
            Homework hw = homeworkList.get(i);
            // 데드라인이 지나지 않았는지 판단 후 컵라면 수 추가
            if(noodles.size() < hw.deadline) noodles.add(hw.noodle);
            // 대체할 문제가 있는지 확인 후 컵라면을 더 많이 받을 수 있다면 대체
            else if(noodles.size() == hw.deadline) {
                if(noodles.peek() < hw.noodle) {
                    noodles.poll();
                    noodles.add(hw.noodle);
                }
            }
        }
		
        // 컵라면 수 모두 더하기
        while(!noodles.isEmpty()) {
            result += noodles.poll();
        }

        System.out.println(result);

    }
}