[백준] 4384번: 공평하게 팀 나누기 -JAVA

문제 바로 가기 > 4384번: 공평하게 팀 나누기

0/1 냅색 알고리즘으로, DP로 풀 수 있다.

이 문제는 '부분집합의 합' 문제의 변형으로 볼 수 있다. 우리의 목표는 전체 무게의 절반에 가장 가까운 부분집합을 찾는 것이다.

1. 2차원 boolean 배열 dp를 사용합니다.
2. dp[i][j]는 i명의 사람을 선택하여 정확히 j 무게를 만들 수 있는지 여부를 나타낸다 (true/false)

알고리즘

1. dp 배열 초기화: dp[0][0] = true (0명으로 0kg을 만들 수 있음)

2. 각 참가자에 대해:

• 1명부터 전체 인원의 절반까지 선택하는 경우를 고려
• 가능한 모든 무게 조합을 계산하여 dp 배열 갱신

for(int i=0; i<n; i++){
    for(int j=n/2; j>0; j--){
        for(int k=totalWeight; k>=weights[i]; k--){
            dp[j][k] = dp[j][k] || dp[j-1][k-weights[i]];
        }
    }
}

 

3. dp[전체 인원의 절반][k]가 true인 k 중 전체 무게의 절반에 가장 가까운 값 선택

for(int k=0;k<=totalWeight;k++){
    if(dp[n/2][k]){
        int a=k;
        int b=totalWeight-a;
        int curDif=Math.abs(a-b);
        if(minDif>curDif){
            minDif=curDif;
            team1weight=k;
        }
    }
}

 

예시

입력이 다음과 같이 주어졌다.

4
30
40
50
60

 

Step1. 배열 초기화

j/k	0
0	T

 

Step2. dp배열 갱신

i = 0 (30kg 참가자 추가)

• j = 2 (2명)
  • k는 180부터 30까지 감소
• j = 1 (2명)
  • k는 180부터 30까지 감소
  • dp[1][30] = dp[1][30] || dp[0][0] = true

j/k	0	30
0	T	F
1	F	T
2	F	F

 

i = 1 (40kg 참가자 추가)

• j = 2 (2명)
  • k는 180부터 40까지 감소 
  • dp[2][70] = dp[2][70] || dp[1][30] = true
• j = 1 (1명)
  • k는 180부터 40까지 감소
  • dp[1][40] = dp[1][40] || dp[0][0] = true

j/k	0	30	40	70
0	T	F	F	F
1	F	T	T	F
2	F	F	F	T

 

i = 2 (50kg 참가자 추가)

• j = 2 (2명)
  • k는 180부터 50까지 감소
  • dp[2][90] = dp[2][90] || dp[1][40] = true
  • dp[2][80] = dp[2][80] || dp[1][30] = true
• j = 1 (1명)
  • k는 180부터 50까지 감소
  • dp[1][50] = dp[1][50] || dp[0][0] = true

j/k	0	30	40	50	70	80	90
0	T	F	F	F	F	F	F
1	F	T	T	T	F	F	F
2	F	F	T	F	T	T	T

 

i = 3 (60kg 참가자 추가)

• j= 2 (2명)
  • k는 180부터 60까지 감소
  • dp[2][120] = dp[2][120] || dp[1][60] = true
  • dp[2][110] = dp[2][110] || dp[1][50] = true
  • dp[2][100] = dp[2][100] || dp[1][40] = true
  • dp[2][90] = dp[2][90] || dp[1][30] = true
• j = 1 (1명)
  • k는 180부터 60까지 감소
  • dp[1][60] = dp[1][60] || dp[0][0] = true

j/k	0	30	40	50	60	70	80	90	100	110	120
0	T	F	F	F	F	F	F	F	F	F	F
1	F	T	T	T	T	F	F	T	F	F	F
2	F	F	T	F	F	T	T	T	T	T	T

 

Step3. dp[전체 인원의 절반][k]가 true인 k 중 전체 무게의 절반에 가장 가까운 값 선택

dp[2][k]가 true인 k중에서 무게의 절반(90)에 가장 가까운 값은 90이다.
따라서 답은 90 90이 된다.

j/k	0	30	40	50	60	70	80	90	100	110	120
2	F	F	T	F	F	T	T	T	T	T	T

전체 코드

import java.io.*;

public class _4384 {

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        int[] weights=new int[n+1];
        int totalWeight=0;
        int minDif=Integer.MAX_VALUE;
        int team1weight=0;
        int team2weight=0;

        for(int i=0;i<n;i++){
            weights[i]=Integer.parseInt(br.readLine());
            totalWeight+=weights[i];
        }
        boolean[][] dp=new boolean[n][totalWeight+1];


        dp[0][0]=true;

        for(int i=0;i<n;i++){
            for(int j=n/2;j>0;j--){
                for(int k=totalWeight;k>=weights[i];k--){
                    dp[j][k]=dp[j][k]||dp[j-1][k-weights[i]];
                }
            }
        }


        for(int k=0;k<=totalWeight;k++){
            if(dp[n/2][k]){
                int a=k;
                int b=totalWeight-a;
                int curDif=Math.abs(a-b);
                if(minDif>curDif){
                    minDif=curDif;
                    team1weight=k;
                }
            }
        }

        team2weight=totalWeight-team1weight;

        if(team1weight>team2weight){
            int temp=team1weight;
            team1weight=team2weight;
            team2weight=temp;
        }

        System.out.println(team1weight+" "+team2weight);

    }
}