[Java] 백준 9423. 레슬링 팀 선발

문제 링크 - https://www.acmicpc.net/problem/9423

 

 

---

 

 

 

 

 

 

문제

대한 레슬링 협회는 다가오는 올림픽 선발전을 대비하기 위해 소속 선수들을 두 팀으로 나누려고 한다.

모든 선수는 두 팀 중 하나에 소속되어야 한다. 또, 두 팀에 소속된 선수의 차이는 1을 넘어갈 수 없다. 마지막으로, 각 팀의 몸무게의 합의 차이는 최소가 되어야 한다.

모든 선수들의 몸무게가 주어졌을 때, 위의 조건을 지키면서 팀을 나눈 다음, 각 팀의 몸무게의 합을 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 선수의 수 n이 주어진다. 다음 n개 줄에는 각 선수의 몸무게가 주어진다. 몸무게는 1보다 크거나 같고, 450보다 작거나 같은 정수이다. 협회에 소속된 선수의 수는 100명을 넘지 않는다.

 

 

출력

각 팀의 몸무게의 합을 공백으로 구분해 출력한다. 합이 작은 것을 먼저 출력한다.

 

 

 

 

 

 

 

 

---

 

풀이

N명을 두 팀으로 나누기 때문에 N/2명을 팀을 배치하게 되면 남은 사람들은 다른 팀이 된다. (편의상 a팀 b팀)
N/2명이 a팀을 이룰 때 가능한 몸무게 합을 모두 구한 뒤, 전체 몸무게 합에서 이 값을 빼면 b팀의 몸무게 합이 나온다.

각 팀의 몸무게의 합의 차이는 최소가 되어야 하므로 팀을 구성하는 것이 가능한 경우를 먼저 체크해 주고, 가능한 경우 중 몸무게 차이의 합이 최소가 되는 경우를 확인하며 갱신해 준다. 

 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

/*
    https://www.acmicpc.net/problem/9423
    
    N/2명을 배치하면 나머지는 자동으로 배정.
    N/2명이 가능한 점수를 모두 구한 뒤 이를 전체 총합에서 뺀 값의 차이를 최소화.
    i번째 사람을 추가하면서 1 ~ N/2명 팀을 구성할 때의 값을 구함.
    N/2 명의 점수 총합의 최댓값은 (최대 인원수 / 2 * 인원당 최대 점수)
    i번째 사람을 추가할 때 i-1번째 사람까지 1~N/2 명이 팀을 이루도록 했을 때 
    가능한 모든 점수에서 추가하는 방식
 */

public class Main {
    static final int MAX_W = 450; // 몸무게 최댓값
    static int N; // 선수의 수
    static int[] weights; // 각 선수의 몸무게

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());

        weights = new int[N];
        int total = 0; // 선수들 몸무게 합
        
        for(int i=0; i<N; i++) {
            weights[i] = Integer.parseInt(br.readLine());
            total += weights[i];
        }

        bw.write(sol(total));
        bw.flush();
        bw.close();
        br.close();
    }//main


    private static String sol(int total) {
        int half = N/2; // 선수 인원 반 (두 팀에 소속된 선수의 차이는 1을 넘어갈 수 없다.)
        int maxW = half * MAX_W; // N/2 명의 점수 총합의 최댓값
        boolean[][] dp = new boolean[half+1][maxW+1];
        dp[0][0] = true;

        for(int i=0; i<N; i++) {
            for(int j=half; j>0; j--) {
                for(int w=maxW; w>=weights[i]; w--) {
                    dp[j][w] |= dp[j-1][w - weights[i]];
                }
            }
        }

        int teamA = 0; // a팀 몸무게 합
        int teamB = 0; // b팀 몸무게 합
        int min = Integer.MAX_VALUE;

        for(int w=0; w<maxW; w++) {
            if(dp[half][w]) {
                // 가능한 무게합이라면 각 팀의 몸무게의 합의 차이 최솟값 비교
                int diff = Math.abs(w - (total-w));
                if(min > diff) {
                    teamA = w;
                    min = diff;
                }
            }
        }

        // 각 팀의 몸무게의 합을 공백으로 구분해 출력 -> 합이 작은 것을 먼저
        teamB = total - teamA;
        if(teamA > teamB) {
            int tmp = teamA;
            teamA = teamB;
            teamB = tmp;
        }

        return teamA + " " + teamB;
    }//sol


}//class