풀이 방법
그리디로 풀어야 하는 문제이지만 무조건 능력이 큰 것부터 넣게 되면 안된다.
반례
1 2 3 4 5
6 6 6 6 6
각 참가자는 공, 수 능력 중 더 큰것을 선택해야 하는데 그러기 위해서는 공, 수 능력의 차이가 가장 큰 것부터 넣어줘야 한다.
우선순위 큐를 이용해서 차이가 더 큰것을 우선순위로 주고 차이가 같다면 값이 더 큰 참가자를 우선으로 해주었다.
내 코드
package com.company;
import java.io.*;
import java.util.*;
public class Main {
static int N, M, T;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
T = Integer.parseInt(br.readLine());
PriorityQueue<int[]> pq = new PriorityQueue<>(
new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (Math.abs(o1[0] - o1[1]) == Math.abs(o2[0] - o2[1])) {
return Math.max(o2[0], o2[1]) - Math.max(o1[0], o1[1]);
}
return Math.abs(o2[0] - o2[1]) - Math.abs(o1[0] - o1[1]);
}
}
);
for (int i = 0; i < T; i++) {
pq.clear();
ArrayList<Integer> A = new ArrayList<>();
ArrayList<Integer> B = new ArrayList<>();
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
boolean[] check = new boolean[N + 1];
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
A.add(Integer.parseInt(st.nextToken()));
}
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
B.add(Integer.parseInt(st.nextToken()));
}
for (int j = 0; j < N; j++) {
pq.offer(new int[]{A.get(j), B.get(j)});
}
long sum = 0;
int a_count = 0;
int b_count = 0;
int x = 0;
for (int j = 1; j <= N / 2 + 1; j++) {
if (N - (2 * j) <= M) {
x = N - j;
break;
}
}
while (!pq.isEmpty()) {
int[] arr = pq.poll();
int a = arr[0];
int b = arr[1];
if ((a >= b && a_count < x) || b_count == x) {
sum += a;
a_count++;
} else if (b_count < x || a_count == x) {
sum += b;
b_count++;
}
}
System.out.println(sum);
}
}
}
'코딩테스트 > [백준] 코딩테스트 연습' 카테고리의 다른 글
문자열 잘라내기 - 2866번 (0) | 2021.11.09 |
---|---|
줄어들지 않아 - 2688번 (0) | 2021.11.09 |
거짓말 - 1043번 (0) | 2021.11.08 |
십자가 2개 놓기 - 17085번 (0) | 2021.11.05 |
Coins - 3067번 (0) | 2021.11.04 |