이번에 풀어본 문제는
백준 17503 맥주 축제 입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Beer {
int prefer, alcohol;
public Beer(int prefer, int alcohol) {
this.prefer = prefer;
this.alcohol = alcohol;
}
}
public class Main {
static int N, M, K;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
Queue<Integer> prefers = new PriorityQueue<>();
List<Beer> beers = new ArrayList<>();
for (int i = 0; i < K; i++) {
st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken());
int a = Integer.parseInt(st.nextToken());
beers.add(new Beer(p, a));
}
beers.sort(new Comparator<Beer>() {
@Override
public int compare(Beer o1, Beer o2) {
if (o1.alcohol == o2.alcohol) {
return o2.prefer - o1.prefer;
}
return o1.alcohol - o2.alcohol;
}
});
int total = 0;
int answer = -1;
for (Beer beer : beers) {
prefers.add(beer.prefer);
total += beer.prefer;
if (prefers.size() > N) {
total -= prefers.poll();
}
if (prefers.size() == N && total >= M) {
answer = beer.alcohol;
break;
}
}
System.out.print(answer);
}
}
N개의 맥주를 선택하여 M 이상의 만족도를 얻을 수 있는 최소 간의 레벨을 구하는 문제입니다.
주어진 K개의 맥주를 알코올 도수 기준으로 오름차순 정렬합니다.
정렬된 맥주를 탐색하면서, 해당 맥주의 선호도를 누적하여 더해주면서, 내림차순으로 정렬된 우선순위큐에 값을 담아줍니다.
이렇게 되면, 도수가 낮은 순서로 맥주를 선택하며, 큐 사이즈가 N값을 초과했다면, 우선순위 큐에서 가장 선호도가 낮은 맥주를 빼내고, 큐 사이즈와 N값이 같아졌을 때, 누적된 값이 M 보다 크다면 바로 탈출할 수 있게됩니다.
이분탐색으로 시도했으나, 시간초과가 발생했습니다..ㅠ