728x90
백준 1781 - 컵라면
https://www.acmicpc.net/problem/1781

문제
N개의 문제를 주고 각각의 문제를 풀었을 때 컵라면 몇 개 줄 것인지 제시
문제를 푸는데는 단위 시간 1 걸리며, 각 문제의 데드라인 <= N
각 문제를 풀 때 받을 수 있는 컵라면 수, 최대로 받을 수 있는 컵라면 수 < $2^{31}$
입력
첫 줄: 숙제의 개수 N (1 <= N <= 200,000)
다음 줄 ~ N + 1 줄: i + 1번째 줄에 i번째 문제에 대한 데드라인, 풀면 받을 수 있는 컵라면 수
출력: 받을 수 있는 최대 컵라면 수
풀이
하루에 한 문제만 풀 수 있고 데드라인 d인 문제는 d일까지 해결해야 함
-> 마감일(`deadline`) 기준으로 가능한 만큼 문제 넣고 IF. 풀이 가능 수 초과 -> 라면 가장 적은 문제 버림
=> 그 시점까지 풀 수 있는 문제 수 넘기면 라면 적은 문제 버림
int[][] arr = new int[N][2];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, (a, b) -> a[0] - b[0]);
- `PriorityQueue<Integer> pQ = new PriorityQueue<>()`: 현재까지 푼 라면 수 저장
- `pq.size() > deadline`: 현재 날짜(`deadline`)보다 더 많이 문제 품
- -> `pQ.poll()`: 가장 적은 라면을 주는 문제 버림
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
int deadline = arr[i][0];
int ramen = arr[i][1];
pQ.add(ramen);
if (pQ.size() > deadline) pQ.poll();
}
코드
import java.io.*;
import java.util.*;
// 컵라면
public class boj_1781 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N][2];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < N; i++) {
int deadline = arr[i][0];
int ramen = arr[i][1];
pQ.add(ramen);
if (pQ.size() > deadline) pQ.poll();
}
long total = 0;
while (!pQ.isEmpty()) total += pQ.poll();
System.out.println(total);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/Graph] 백준 1043 - 거짓말 (Java) (0) | 2025.12.04 |
|---|---|
| [BOJ/Graph] 백준 5214 - 환승 (Java) (0) | 2025.12.04 |
| [BOJ/Floyd-Warshall] 백준 1507 - 궁금한 민호 (Java) (0) | 2025.11.28 |
| [BOJ/Floyd-Warshall] 백준 13168 - 내일로 여행 (Java) (0) | 2025.11.27 |
| [BOJ/Floyd-Warshall + DFS] 백준 17182 - 우주 탐사선 (Java) (0) | 2025.11.27 |