문제 링크
문제
티어: 골드 3
알고리즘: 그리디, 정렬
사내 해커톤 대회에서 팀 배틀 보안 해커톤을 하기로 했다.
대회는 주어진 보안 서버를 공격(해킹)하는 역할의 팀 A와 방어(보안)하는 역할의 팀 B로 나누어서 진행한다. 참가자는 총 n명이고, 각 참가자의 공격 능력과 방어 능력은 검증된 사내 테스트를 통해 수치화 되어있다.
참가자는 1부터 n까지 번호가 매겨져 있고, Ai, Bi는 양의 정수로 참가자 i의 공격 능력과 방어 능력을 의미한다.
n명의 참가자를 팀 A와 팀 B로 아래 조건을 지키면서 나누어야 한다.
- 두 팀에 배정된 참가자 수의 차이는 k 이하가 되어야 한다.
- 각 참가자는 두 팀 중 하나에 반드시 속해야한다.
- 위의 두 조건을 만족하는 모든 팀 배정 방법 중, 팀 A에 배정된 참가자들의 공격 능력 총 합과 팀 B에 배정된 참가자들의 방어 능력치 총 합이 최대가 되어야 한다.
예를 들어, n = 3, k = 1이고, 세 참가자의 공격 능력과 방어 능력이 아래와 같은 경우를 살펴보자.
- A1 = 1, B1 = 100
- A2 = 100, B2 = 99
- A3 = 80, B3 = 95
k = 1이기 때문에, 팀 A와 팀 B에는 각각 1명과 2명이 배정되어야 한다.
총 여섯 가지 방법이 가능하며 팀 구성과 능력치의 합은 아래와 같다.
- 팀 A: [1], 팀 B: [2, 3], 능력치의 합 = A1 + B2 + B3 = 195
- 팀 A: [2], 팀 B: [1, 3], 능력치의 합 = A2 + B1 + B3 = 295
- 팀 A: [3], 팀 B: [1, 2], 능력치의 합 = A3 + B1 + B2 = 279
- 팀 A: [2, 3], 팀 B: [1], 능력치의 합 = A2 + A3 + B1 = 280
- 팀 A: [1, 3], 팀 B: [2], 능력치의 합 = A1 + A3 + B2 = 180
- 팀 A: [1, 2], 팀 B: [3], 능력치의 합 = A1 + A2 + B3 = 196
두 번째 방법이 가장 높은 능력치 합을 가진다.
n, k, 그리고 각 참가자의 공격과 방어 능력치가 주어졌을 때, 가능한 모든 팀 배정 방식 중에서 능력치 합의 최댓값을 구해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫째 줄에는 n과 k가 공백으로 구분되어 주어진다. 둘째 줄에는 참가자의 공격 능력을 나타내는 A1, A2, ..., An이 주어지고, 셋째 줄에는 방어 능력을 나타내는 B1, B2, ..., Bn이 주어진다.
출력
각 테스트 케이스 마다 능력치 합의 최댓값을 한 줄에 하나씩 출력한다.
제한
- 1 ≤ T ≤ 10
- 3 ≤ n ≤ 100,000
- 1 ≤ k ≤ n-2
- 1 ≤ Ai, Bi ≤ 1,000,000
풀이
구해야 하는 것은 가능한 모든 팀 배정 방식 중에서 능력치 합의 최댓값이다.
제한을 보면 완탐은 불가능하다.
능력치 합의 최댓값(공 + 방)을 최대로 하려면 어떻게 해야 할까?
사람마다 공, 방의 차이 중 더 큰 것을 더한다면? k조건은 만족하지 않을 수 있지만 팀 배정 방식 중에는 최댓값이 될 것이다.
예를 들어
3 1
2 5
4 2
라고 했을 때
첫 번째 사람과 세 번째 사람은 공이 더 크기 때문에 공을 더해주고, 두 번째 사람은 방이 더 크기 때문에 방을 더해준다. 당연히 이 값은 최댓값이 될 수밖에 없다.
그러면 k조건이 만족하지 않을 수 있기 때문에 이 조건을 만족시키면 된다.
k조건이 만족하지 않는다는 것을 더 구체적으로 말하면, 공이 더 큰 사람과 방이 더 큰 사람의 차이가 k보다 크다는 것이다. 그리고 이 배정 방식은 최댓값이다.
그러면 k 이하로 만들어 주려면 더 큰 사이즈의 있는 사람을 더 작은 사이즈의 있는 사람으로 옮겨주면 된다. 그래야 차이가 줄어들기 때문에
어떤 사람을 옮겨야 할까? 공, 방 차이가 더 작은 사람을 옮겨주는 게 최선의 선택이다.
왜냐하면 공 방의 차이가 더 큰 사람을 옮겨주면 그 차이만큼 값이 감소하기 때문에 당연한 선택이다.
언제까지 옮겨야 할까? k 이하가 되는 최초 지점까지 옮겨야 한다.
왜냐하면 k 이하로 맞춰주는 작업은 더 큰 스탯이 아닌 더 작은 스탯을 값에 포함하는 작업이기 때문에 최대한 적게 반복해 줘야 한다.
그러면 앞에서 설명한 방식으로 답을 구해보겠다.
5 2
1 3 5 7 9
1 2 3 4 5
일 때
공이 더 큰 사람
1 1 -> 차이 0
3 2 -> 차이 1
5 3 -> 차이 2
7 4 -> 차이 3
9 5 -> 차이 4
방이 더 큰 사람
없음
이 경우 k 조건은 만족하지 않지만 배정 방식 중 최댓값이 된다. 25
k조건을 만족하려면 공 -> 방으로 사람을 옮겨줘야 한다. 이때 차이가 작은 사람을 우선적으로 k이하가 되는 최초 지점까지 반복해 준다.
그러면 다음과 같이 된다.
공이 더 큰 사람
5 3 -> 차이 2
7 4 -> 차이 3
9 5 -> 차이 4
방이 더 큰 사람
1 1 -> 차이 0
3 2 -> 차이 1
3 - 2 <= 2(k) 이기 때문에 조건을 만족한다.
그래서 최종적으로 값은 5 + 7 + 9 + 1 + 2 = 24다.
시간 복잡도는 O(nlogn)이다.
소스 코드
import java.io.*;
import java.util.*;
class Stats implements Comparable<Stats> {
int A,B;
int diff;
Stats(int A, int B) {
this.A = A;
this.B = B;
this.diff = Math.abs(A - B);
}
@Override
public int compareTo(Stats o) {
if(this.diff < o.diff) {
return 1;
} else if(this.diff > o.diff) {
return -1;
}
return 0;
}
}
public class Main {
static int T;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int j=0; j<T; j++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
ArrayList<Stats> aList = new ArrayList<>();
ArrayList<Stats> bList = new ArrayList<>();
StringTokenizer stA = new StringTokenizer(br.readLine());
StringTokenizer stB = new StringTokenizer(br.readLine());
for(int i=0; i<n; i++) {
int A = Integer.parseInt(stA.nextToken());
int B = Integer.parseInt(stB.nextToken());
if(A >= B) {
aList.add(new Stats(A, B));
} else {
bList.add(new Stats(A, B));
}
}
Collections.sort(aList);
Collections.sort(bList);
sb.append(answer(aList, bList, k)).append("\n");
}
System.out.println(sb.toString().trim());
}
static long answer(ArrayList<Stats> aList, ArrayList<Stats> bList, int k) {
int listDiff = Math.abs(aList.size() - bList.size());
//k 이하로 맞춰줘야 됨
while(listDiff > k) {
if(aList.size() > bList.size()) {
//a가 더 많은 경우
bList.add(aList.get(aList.size() - 1));
aList.remove(aList.size() - 1);
} else {
//b가 더 많은 경우
aList.add(bList.get(bList.size() - 1));
bList.remove(bList.size() - 1);
}
listDiff -= 2;
}
long result = 0;
for(int i=0; i<aList.size(); i++) {
result += aList.get(i).A;
}
for(int i=0; i<bList.size(); i++) {
result += bList.get(i).B;
}
return result;
}
}