[백준] 컵라면

[hye-on]

🔗 컵라면

[hye-on]

📑 댓글 템플릿

• Language : C++
• 성능

코드 풀이

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

//1:20 ~2:36
int n;

priority_queue<pair<int, int>>pq;//데드라인, 컵라면
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	int a = 0, b = 0;
	int ans = 0;
	int today = 0;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		pq.push({ a,b });
		today = max(a, today);
		
	}

	priority_queue<int>frontDay;
	while (today>=1 ) { //틀린 이유 : pq가 empty더라도 계속 돌아야함 
		
		
		while (!pq.empty() &&today <= pq.top().first) {
			
			frontDay.push({ pq.top().second});
			pq.pop();
		}
		if (!frontDay.empty()) {
			ans += frontDay.top();
			
			frontDay.pop();
			
		}
		today--;
	}

	cout << ans;
}

코멘트

- 문제가 조금 이해하기 어려웠습니다.

[uijin-j]

📑 댓글 템플릿

• Language : Java
• 성능

코드 풀이

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

// 22:00 시작!
public class Main
{
    /**
     * 우선순위 큐? 실제 시간이 가는 것을 t로 나타내기
     */
	public static void main(String[] args) throws Exception {
	    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	    int n = Integer.parseInt(bf.readLine());
	    int[][] problems = new int[n][2];
	    StringTokenizer st;
	    for(int i = 0; i < n; ++i) {
	        st = new StringTokenizer(bf.readLine());
	        problems[i][0] = Integer.parseInt(st.nextToken());
	        problems[i][1] = Integer.parseInt(st.nextToken());
	    }
	    
	    Arrays.sort(problems, (a, b) -> b[0] - a[0]); // 데드라인순으로 내림차순

	    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
	    int idx = 0;
	    int t = problems[0][0];
	    int total = 0;
	    while(t > 0) {
	        while(idx < n && problems[idx][0] >= t) {
	            pq.offer(problems[idx++]);
	        }
	        
	        if(!pq.isEmpty()) {
	            int[] solved = pq.poll();
	            total += solved[1];   
	        }
	        
	        t--;
	    }
	    
	    System.out.println(total);
	}
}

코멘트

- 우선순위큐 자료구조를 사용하는 문제입니다! 유형을 알고 있던 문제라 빨리 푼 것 같습니다!