[BJ 18768] 팀 배정

    서론

    최근에 그리디 알고리즘 문제를 집중적으로 풀어보고 있습니다. 그리디 알고리즘을 사용하는 문제라고 파악이 되면, 어떤 기준을 가지고 최적의 선택을 해야할지 고민해 보아야 합니다. 이 문제는 쉽게 풀 수 있을 것 처럼 보이는 문제지만 기준을 정교하게 세워야 통과할 수 있는 문제입니다.

    www.acmicpc.net/problem/18768

     

    18768번: 팀 배정

    각 테스트 케이스 마다 능력치 합의 최댓값을 한 줄에 하나씩 출력한다.

    www.acmicpc.net

    [팀 배정]

    문제

    사내 해커톤 대회에서 팀 배틀 보안 해커톤을 하기로 했다.

    대회는 주어진 보안 서버를 공격(해킹)하는 역할의 팀 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명이 배정되어야 한다.

    총 여섯 가지 방법이 가능하며 팀 구성과 능력치의 합은 아래와 같다.

    1. 팀 A: [1], 팀 B: [2, 3], 능력치의 합 = A1 + B2 + B3 = 195
    2. 팀 A: [2], 팀 B: [1, 3], 능력치의 합 = A2 + B1 + B3 = 295
    3. 팀 A: [3], 팀 B: [1, 2], 능력치의 합 = A3 + B1 + B2 = 279
    4. 팀 A: [2, 3], 팀 B: [1], 능력치의 합 = A2 + A3 + B1 = 280
    5. 팀 A: [1, 3], 팀 B: [2], 능력치의 합 = A1 + A3 + B2 = 180
    6. 팀 A: [1, 2], 팀 B: [3], 능력치의 합 = A1 + A2 + B3 = 196

    두 번째 방법이 가장 높은 능력치 합을 가진다.

    n, k, 그리고 각 참가자의 공격과 방어 능력치가 주어졌을 때, 가능한 모든 팀 배정 방식 중에서 능력치 합의 최댓값을 구해보자.

    핵심 아이디어로 접근하는 과정

    단순하게 생각하기

     

    처음에는 참가자의 공격/수비 중 더 큰 능력을 기준으로 내림차순 정렬을 하여 그때그때 뽑으면 되지 않을까 생각했습니다. 정렬엔 PriorityQueue를 이용하였습니다. 그러나 여기엔 치명적인 문제가 있습니다.

    PriorityQueue<int[]> pq = new PriorityQueue<>(
    	new Comparator<int[]> (){
            @Override
            public int compare(int[] o1, int[] o2) {
                if(Math.max(o2[0],o2[1])==Math.max(o1[0],o1[1])) {
                    return Integer.compare(Math.abs(o2[0]-o2[1]),Math.abs(o1[0]-o1[1]));
                }
                return Integer.compare(Math.max(o2[0],o2[1]),Math.max(o1[0],o1[1]));
            }
         }
     }

    다음 능력치를 가진 두 사람을 생각해 보겠습니다. n=2, k=1

     

    A : 공격-99 수비-100

    B : 공격-1  수비-99

     

    처음 고안한 알고리즘은 A를 수비팀으로, B를 공격팀으로 배정할 것입니다. 능력치 총 합은 101이 되지만 직관적으로 알 수 있는 정답은 A를 공격으로, B를 수비로 놓아 198의 최대 능력치를 얻는 것입니다. 능력치의 최댓값을 기준으로 뽑는 것은 문제 풀이에 실패할 수 있습니다.

     

    조금 더 정교하게 생각하기

     

    위의 예제를 이어가겠습니다. 최댓값을 기준으로 부분적인 해를 기준으로 하였을 때, 낮은 쪽의 능력치가 탐욕적인 해의 유망한 후보임에도 불구하고 고려 대상이 아닙니다. 다른 기준으로 정렬이 필요하다고 생각을 하다가 떠올린 아이디어는,  공격과 수비 능력치 차이의 절대값을 기준으로 삼는 것입니다. A를 공격으로 뽑지 않고 수비로 뽑았을 때 얻는 이득은 얼마인가?를 생각해보시면, 1의 이득을 가질 수 있습니다. 마찬가지로 B를 수비로 뽑지않고 공격으로 뽑으면 최댓값에서 99만큼 손해를 보게 됩니다. 항상 이득을 최대로 가져갈 수 있는 선택을 매 순간 해준다면, 최적해를 얻을 수 있습니다. 

     

    A에서 얻거나 잃게되는 이득은 1, B에서 98이 됩니다.

    B에서 이득을 가져가기 위해 공격/수비 중 큰 값의 능력치를 취하고, B를 수비팀으로 넣는 것과 동일합니다.

    그 다음 차례인 A는 알고리즘이 공격팀으로 편성할 것이지만, B가 이미 수비팀으로 들어갔고, 양 팀원 수의 차이는 1 이하를 만족하기 때문이기도 합니다.

    PriorityQueue<int[]> pq = new PriorityQueue<>(
    	new Comparator<int[]> (){
    
    		@Override
    		public int compare(int[] o1, int[] o2) {
    			if(Math.abs(o2[0]-o2[1])==Math.abs(o1[0]-o1[1])) {
    				return Integer.compare(Math.max(o2[0],o2[1]), Math.max(o1[0],o1[1]));
    			}
    			return Integer.compare(
    				Math.abs(o2[0]-o2[1]), 
    				Math.abs(o1[0]-o1[1]));
    		}
    	}
    }

     

    팀원 수 차이 k 이하로 유지하기

     

    팀원 수를 k 이하로 유지하는 아이디어는 간단합니다. 한 팀에 들어갈 수 있는 최대 인원수를 구한 다음, 양 팀중 어느 한쪽이 최대 인원수를 알고리즘에 의해 먼저 채울 경우, 어느 팀에도 편성되지 않은 나머지 인원 모두는 반대편 팀으로 편성하는 것입니다. n과 k가 짝수/홀수일 때 공식이 달라지므로 직접 케이스 분류를 하면서 이해하시면 좋겠습니다.

    if(N % 2 == 1 && K % 2 == 1) {
    	max = N - N/2 + K/2;
    }
    else {
    	max = N/2 + K/2;
    }

    이득이 0인 경우의 예외처리

     

    만약 공격과 수비 능력치가 같은 경우는 어떻게 처리해야 할까요? 이런 사람은 어느 팀에 넣어도 결과값에 영향을 주지 않습니다. 정답(능력치 최댓값)에 더해주시고, 공격/수비 팀원 카운트 어느 쪽에도 추가하지 않습니다. 만약 한 쪽 팀이 최대 인원을 채운다면, 반대편 팀에 모두 편성해주면 되기 때문입니다. 반대의 경우도 마찬가지입니다.

    그리고 현재 아이디어에서는 이득이 0인 경우는 우선순위 큐에서 마지막에 등장합니다. 그 말은 처음 공격과 수비 능력치가 같은 사람이 등장한 이후의 사람들은 상황에 따라 다른 팀에 집어넣을 경우 결과에 영향을 주지 않는 능력치 분배를 가지고 있습니다.

    저는 0인 경우를 따로 처리하였지만, 별도로 처리를 해주지 않아도 큰 문제가 없을 것입니다.

     

    코드

    피드백은 언제나 환영합니다.

    import java.io.*;
    import java.util.*;
    
    public class Main {
    
    	public static void main(String[] args) throws Exception{
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    		StringBuilder sb = new StringBuilder();
    		PriorityQueue<int[]> pq = new PriorityQueue<>(
    				new Comparator<int[]> (){
    
    					@Override
    					public int compare(int[] o1, int[] o2) {
    						if(Math.abs(o2[0]-o2[1])==Math.abs(o1[0]-o1[1])) {
    							return Integer.compare(Math.max(o2[0],o2[1]), Math.max(o1[0],o1[1]));
    						}
    						return Integer.compare(
    								Math.abs(o2[0]-o2[1]), 
    								Math.abs(o1[0]-o1[1]));
    					}
    				}
    			);
    		int T  = Integer.parseInt(br.readLine());
    		for(int tc = 0; tc < T; tc++) {	
    			StringTokenizer st = new StringTokenizer(br.readLine());
    			pq.clear();
    			int N = Integer.parseInt(st.nextToken());
    			int K = Integer.parseInt(st.nextToken());
    			long max = 0;
    			if(N % 2 == 1 && K % 2 == 1) {
    				max = N - N/2 + K/2;
    			}
    			else {
    				max = N/2 + K/2;
    			}
    		
    			int[] tmp = new int[N];
    			st = new StringTokenizer(br.readLine());
    			for(int i = 0; i < N; i++) {
    				tmp[i] = Integer.parseInt(st.nextToken());
    			}
    			st = new StringTokenizer(br.readLine());
    			for(int i = 0; i < N; i++) {
    				pq.offer(new int[] {Integer.parseInt(st.nextToken()), tmp[i]});
    			}
    			int ta = 0;
    			int tb = 0;
    			long sum = 0;
    			while(!pq.isEmpty()) {
    				int[] curr = pq.poll();
    				if(ta == max) {
    					tb++;
    					sum += curr[1];
    				}
    				else if(tb == max) {
    					sum += curr[0];
    					ta++;
    				}
    				else {
    					if(curr[0]>curr[1]) {
    						ta++;
    					}
    					else if (curr[0]<curr[1]) {
    						tb++;
    					}
    					sum+= Math.max(curr[0], curr[1]);
    				}
    			}
    			sb.append(sum+"\n");
    		}
    		bw.write(sb.toString());
    		bw.flush();
    		br.close();
    		bw.close();
    	}
    
    }
    

     

    'IT > Algorithm' 카테고리의 다른 글

    [BOJ 17839] Baba is Rabbit  (0) 2021.03.04
    [BJ 3344] N-Queens  (0) 2021.02.24
    [BOJ 1256] 사전 (풀이 미완성, DP사용 X)  (0) 2021.02.10
    [BOJ 3078] 좋은 친구  (0) 2021.02.04
    [BOJ 4884] FIFA 월드컵  (0) 2021.01.23

    댓글