컵라면
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 256 MB 9153 2702 2028 30.990%
문제
상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라인을 정하였다.
문제 번호 1 2 3 4 5 6 7
데드라인 1 1 3 3 2 2 6
컵라면 수 6 7 2 1 4 5 1
위와 같은 상황에서 동호가 2, 6, 3, 1, 7, 5, 4 순으로 숙제를 한다면 2, 6, 3, 7번 문제를 시간 내에 풀어 총 15개의 컵라면을 받을 수 있다.
문제는 동호가 받을 수 있는 최대 컵라면 수를 구하는 것이다. 위의 예에서는 15가 최대이다.
문제를 푸는데는 단위 시간 1이 걸리며, 각 문제의 데드라인은 N이하의 자연수이다. 또, 각 문제를 풀 때 받을 수 있는 컵라면 수와 최대로 받을 수 있는 컵라면 수는 모두 231보다 작거나 같은 자연수이다.
입력
첫 줄에 숙제의 개수 N (1 ≤ N ≤ 200,000)이 들어온다. 다음 줄부터 N+1번째 줄까지 i+1번째 줄에 i번째 문제에 대한 데드라인과 풀면 받을 수 있는 컵라면 수가 공백으로 구분되어 입력된다.
출력
첫 줄에 동호가 받을 수 있는 최대 컵라면 수를 출력한다.
풀이
문제의 핵심은 데드라인을 완수하며 문제를 풀었을 때 얻을 수 있는 최대 컵라면의 수이다.
핵심은 데드라인이 작은 순, 데드라인이 같다면 컵라면이 많은 순으로 줄세운 후 한 문제씩 택하는 것이다.
그러나 주의할 점은 데드라인이 작은 것을 택하는 것보다 데드라인이 큰 문제를 택할 때 컵라면의 수가 더 많을 수 있다는 점이다.
그래서 나는 다음과 같이 문제를 해결하였다.
- 문제 큐(데드라인, 컵라면 수로 정렬), 정답 큐(컵라면 수로 정렬)
- 문제를 풀 때마다 시간을 1초씩 증가시킴
3-1. 문제 큐에서 꺼냇을 때 시간이 데드라인보다 작다면 해당 문제를 푼 문제에 넣음
3-2. 문제 큐에서 꺼냇을 때 시간이 데드라인과 같다면 정답 큐에서 가장 작은 값과 비교하여 문제의 컵라면 값이 크다면 바꿔치기함
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static class Question implements Comparable<Question> {
int deadLine;
long lamen;
public Question(int deadLine, int lamen) {
this.deadLine = deadLine;
this.lamen = lamen;
}
@Override
public int compareTo(Question o) {
return this.deadLine == o.deadLine
? lamenCompare(o)
: this.deadLine - o.deadLine;
}
@Override
public String toString() {
return "Question{" +
"deadLine=" + deadLine +
", lamen=" + lamen +
'}';
}
private int lamenCompare(Question o) {
if (o.lamen > this.lamen) {
return 1;
}
return 0;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Question> pq = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
pq.add(new Question(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
}
PriorityQueue<Long> lamens = new PriorityQueue<>();
int time = 0;
while (!pq.isEmpty()) {
Question question = pq.poll();
if (question.deadLine > time) {
lamens.add(question.lamen);
time++;
} else if (question.deadLine == time) {
if (lamens.peek() < question.lamen) {
lamens.poll();
lamens.add(question.lamen);
}
}
}
long ans = 0;
for (Long lamen : lamens) {
ans += lamen;
}
System.out.println(ans);
}
}
'알고리즘' 카테고리의 다른 글
1107 리모컨 JAVA (0) | 2022.10.28 |
---|---|
1759 암호 만들기 JAVA (0) | 2022.10.25 |
16235 나무 재테크 (Java) (0) | 2022.07.01 |
10844 쉬운 계단 수 (0) | 2022.06.27 |
17779 게리맨더링 2 (Java) (0) | 2022.06.20 |