BOJ 4384 공평하게 팀 나누기

* BOJ 4384 공평하게 팀 나누기

[분류 : 다이나믹 프로그래밍]

[풀이]

  N/2명을 배치하면 나머지 N/2+N%2명은 자동으로 배정된다. 따라서 N/2명이 가능한 점수를 모두 구한 뒤 이를 전체 총합에서 뺀 값과의 차이를 최소화하면 되시겠다.

  동전 교환 문제처럼 생각해보자.

  i번째 사람을 추가하면서 1~N/2명팀을 구성할 때의 값을 구한다. N/2명의 점수 총합의 최대값은 최대 인원수 / 2 * 인원당 최대 점수로 계산 가능하다. 

  계산해보면 알겠지만, 수 자체가 배열에 담기에 충분히 작기 때문에, i번째 사람을 추가할 때 i-1번째 사람까지 1~N/2명을 팀을 이루도록 했을 때의 "가능한 모든 점수"에서 추가하는 방식으로 진행하면 된다.

이렇게 N번째 사람까지 N/2명으로 구성했을 때의 가능한 점수를 가지고 반대편 팀을 구한 뒤 여기서의 최소값을 구해주면 된다.

※ 주의해야할 점은 인원수를 오름차순으로 방문하면 데이터가 오염될 수 있기 때문에 인원수를 내림차순으로 방문해야 한다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 100, MAX_K = 450, MAX_W = MAX_N / 2 * MAX_K;
int main() {
	freopen("input.txt", "r", stdin);
	int N, K[MAX_N], i, j, k, t = 0, a = 1e9, b, diff = 1e9;
	bool dp[51][MAX_W + 1] = {};
	scanf("%d", &N);
	for (i = 0; i < N; i++){
		scanf("%d", &K[i]);
		t += K[i];
	}
	dp[0][0] = 1;
	for(i=0;i<N;i++) for(j=N/2;j;j--) for(k=MAX_W; k>=K[i];k--)
		dp[j][k] |= dp[j - 1][k - K[i]];
	for(k=0;k<MAX_W;k++) if(dp[N/2][k])
		if(diff > abs(t - 2 * k)) {
			diff = abs(t - 2 * k);
			a = k;
		}
	b = t - a;
	if(a > b) swap(a, b);
	printf("%d %d",a, b);
	return 0;
}