Step-by-Step
[Java] 백준 1781 - 컵라면 본문
https://www.acmicpc.net/problem/1781
1781번: 컵라면
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라
www.acmicpc.net
여러 가지 반례를 생각해보아야 하는 문제
이 반례를 보고 도움이 많이 됐다 → https://www.acmicpc.net/board/view/97635
예를 들어)
- deadLine 1 cup 2
- deadLine 2 cup 4 / deadLine 2 cup 5 인 경우
데드라인 1에서 1개, 데드라인 2에서 1개를 선택하면 cup이 2+5 = 7이지만,
데드라인 2에서 2개를 선택하면 cup이 4+5 = 9이다.
[방법]
1. PQ 두 개 사용
- PQ 1. 입력값 : deadLine이 짧은 순 → cup라면이 많은 순
- PQ 2. 결과값 : cup라면이 적은 순
2. PQ 1에서 꺼내서 PQ 2에 넣기
- PQ 1에서 하나씩 꺼내와 PQ 2에 넣음
3. 작업의 개수(=소요 시간)가 PQ 1에서 꺼낸 작업의 마감기한보다 크거나 같은 경우
- PQ 2의 맨 앞의 작업의 cup 개수가 PQ 1에서 꺼내온 작업의 cup 개수보다 작으면 PQ 2의 맨 앞 작업을 꺼낸 후 PQ 1에서 꺼낸 작업을 PQ 2에 넣어줌
- 위와 반대일 경우 그냥 continue
[구현]
package BOJ_1000;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
public class boj1781 {
static class Problem implements Comparable<Problem> {
int limit;
int cup;
public Problem (int limit, int cup) {
this.limit = limit;
this.cup = cup;
}
@Override
public int compareTo(Problem o) {
if(this.limit == o.limit)
return o.cup - this.cup;
return this.limit - o.limit;
}
}
private static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
PriorityQueue<Problem> pq = new PriorityQueue<>();
PriorityQueue<Problem> res = new PriorityQueue<>(new Comparator<Problem>() {
@Override
public int compare(Problem o1, Problem o2) {
return o1.cup - o2.cup;
}
});
for(int i=0; i<N; i++) {
String[] str = br.readLine().split(" ");
int l = Integer.parseInt(str[0]);
int c = Integer.parseInt(str[1]);
pq.add(new Problem(l,c));
}
int time = 0, ans = 0;
while(!pq.isEmpty()) {
Problem p = pq.poll();
if(time >= p.limit) {
if(res.peek().cup < p.cup) {
ans -= res.poll().cup;
ans += p.cup;
res.add(p);
}
continue;
}
res.add(p);
ans += p.cup;
time++;
}
System.out.println(ans);
}
}
'언어 > JAVA' 카테고리의 다른 글
[Java] Daily LeetCode Challenge 904. Fruit Into Baskets (0) | 2023.02.07 |
---|---|
[Java] 백준 14908 - 구두 수선공 (0) | 2023.01.31 |
[Java] 백준 3661 - 생일 선물 (0) | 2023.01.26 |
[Java] 백준 23255 - 구름다리2 (0) | 2023.01.19 |
[Java] 백준 17825 - 주사위 윷놀이 (0) | 2023.01.17 |
Comments