BOJ_4384_공평하게 팀 나누기 (Java)

[Gold I] 공평하게 팀 나누기 - 4384

문제 링크

성능 요약

메모리: 36892 KB, 시간: 188 ms

분류

다이나믹 프로그래밍, 배낭 문제

제출 일자

2025년 2월 10일 23:55:01

문제 설명

학생회장을 하고 있는 상근이는 이번 학교 축제 행사로 학우들간의 친밀감을 돈독히 하고자 줄다리기를 하려 한다.

하지만 이 줄다리기에 형평성을 최대한 고려하기위해 두 팀간의 사람 수 차이를 1 이하로 하려하며, 두 팀간의 몸무게의 차이가 최소화되도록 하고자 한다.

이때 상근이가 나누려 하는 두 팀의 몸무게를 각각 출력 하시오.

입력

가장 첫 번째 줄에 줄다리기를 하기 원하는 총 인원의 수(1 ≤ N ≤ 100)가 주어진다.

이후 N개의 줄에 줄다라기에 참여하기 원하는 사람의 몸무게(1 ≤ K ≤ 450)가 주어진다.

출력

두팀의 몸무게를 작은 순서대로 순차적으로 출력한다.

문제 풀이

각 사람(i)에 대해 두 가지 선택이 가능합니다

1. 팀 A에 포함시키지 않는 경우 (팀 B에 포함)
2. 팀 A에 포함시키는 경우

• Math.abs(N/2 - (teamACnt[i-1][j-w[i]]+1)): i번째 사람을 팀 A에 추가했을 때, 이상적인 팀 크기(N/2)와의 차이
• Math.abs(N/2 - teamACnt[i][j]): 현재 상태에서 팀 A의 크기와 이상적인 팀 크기(N/2)와의 차이
• Math.abs((N-N/2) - (teamACnt[i-1][j-w[i]]+1)): i번째 사람을 팀 A에 추가했을 때, 팀 A의 크기와 팀 B의 이상적인 크기(N-N/2)와의 차이
• Math.abs((N-N/2) - teamACnt[i][j]): 현재 상태에서 팀 A의 크기와 팀 B의 이상적인 크기(N-N/2)와의 차이

즉, i번째 사람을 팀 A에 포함시키는 것이 전체적으로 더 균형 잡힌 팀 구성을 만드는 경우에만 이 상태를 선택합니다.

코드

package BOJ_4384_공평하게팀나누기;

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, w[], totalW, teamACnt[][], gap = Integer.MAX_VALUE, finalA, finalB;
    static boolean[][] dp; 
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
//        br = new BufferedReader(new InputStreamReader(System.in));
        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_4384_공평하게팀나누기/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        w = new int[N+1];
        for(int i = 1; i <= N; i++) {
            w[i] = Integer.parseInt(br.readLine());
            totalW += w[i];
        }

        dp = new boolean[N+1][totalW+1]; // dp[i][j]: i명까지 고려했을 때, 팀 A의 몸무게 합이 j가 되는 경우가 가능한지
        teamACnt = new int[N+1][totalW+1]; // teamACnt[i][j]: i명까지 고려했을 때, 팀 A의 몸무게 합이 j일 때 팀 A에 속한 사람 수

        dp[0][0] = true;
        for (int i = 1; i <= N; i++) {
            for(int j = 0; j <= totalW; j++) {
            	// 경우 1: i번째 사람을 팀 A에 포함시키지 않음
                if(dp[i-1][j]) {
                    dp[i][j] = true;
                    teamACnt[i][j] = teamACnt[i-1][j];
                }
                
                // 경우 2: i번째 사람을 팀 A에 포함시킴
                if(j-w[i]>=0 && dp[i-1][j-w[i]]) { // 더 균형잡힌 팀 구성도 고려해야함
                    if(Math.abs(N/2 - (teamACnt[i-1][j-w[i]]+1)) < Math.abs(N/2 - teamACnt[i][j])
                    && Math.abs((N-N/2) - (teamACnt[i-1][j-w[i]]+1)) < Math.abs((N-N/2) - teamACnt[i][j])){
                        dp[i][j] = true;
                        teamACnt[i][j] = teamACnt[i-1][j-w[i]] +1;
                    }
                }
            }
        }

        for(int a_w = 1; a_w <= totalW; a_w++) {
        	// 팀 A의 인원수가 조건(N/2 또는 N-N/2)에 맞고, 해당 몸무게 조합이 가능한 경우
            if((teamACnt[N][a_w] == N/2 || teamACnt[N][a_w] == (N - N/2))&& dp[N][a_w]){
                if(Math.abs(a_w - (totalW - a_w)) < gap){
                    finalA = a_w;
                    finalB = totalW - a_w;
                    gap = Math.abs(a_w - (totalW - a_w));
                }
            }
        }
        if(finalA > finalB) {
            int tmp = finalA;
            finalA = finalB;
            finalB = tmp;
        }
        bw.write(String.valueOf(finalA) + " " + finalB);
        bw.flush();
        bw.close();
        br.close();
    }
}