백준 4384 - 공평하게 팀 나누기 (C++)

 

아... 너무 어렵다 DP

 

기존에 DP문제는 뭔가 특정 시점의 상태값에 대해 더 더하거나 빼거나 해서 다음 상태값을 결정하는 거였는데, 이건 새로운 느낌의 DP문제였다.

 

우선 큰 그림은

몸무게들의 총합을 구해서 (총 사람수 n / 2) 명으로 최대한 (몸무게의 총합 / 2)에 가깝게 만들기

이다.

 

일단 dp 테이블은 dp [한 팀에 최대로 들어갈 수 있는 사람 수][최대 몸무게]로 정했다. 각 dp [i][j]에서 값은 해당 사람 수(i)에서 무게(j)를 만들 수 있으면 1, 없으면 0으로 정했다.  이때 dp [0][0] 즉 0명으로 무게 0을 만들 수 있으므로 dp[0][0]=1로 잡고 시작했다.

 

그다음에 입력받은 무게들에 대해 dp를 돌려줘야 하는데,

 

우선 입력값은 다음과 같다.

 

4
1
2
3
5

 

이러면 정답은? 2+3=5, 1+5=6으로 나와야 할 것이다.

 

for (auto weight : weights) {
    for (int i = 1; i <= n / 2; i++) {
        for (int j = weight; j <= weight_sum; j++) {
            if (dp[i - 1][j - weight]) {
                dp[i][j] = 1;
            }
        }
    }
}

 

이런 식으로 사람 명 수에 대해 1 ➡️ n/2로 순방향으로 탐색이 이루어진다고 생각해 보자.

 

1	0	0	0	0
0	0	0	0	0
0	0	0	0	0

 

그러면 무게 weight = 1이라면 dp [0][0] = 1이니까

 

1	0	0	0	0
0	1	0	0	0
0	0	0	0	0

 

dp [1][1] = 1이 되고, 즉 무게 1짜리 만드는데 무게 1이 사용된 상태이고

 

그다음에 무게 2짜리를 만들 때(i=2 일 때)는 dp [1][1] = 1이므로

 

1	0	0	0	0
0	1	0	0	0
0	0	1	0	0

 

dp [2][2] = 1이 되어버린다. 여기에서 문제는 무게 2짜리를 만들 때 1을 두 번 써버린 걸로 된다. 실제로 위 입력값에서는 2가 있기에 문제가 되진 않지만 예를 들어

 

3
100
90
200

 

예를 들어 위와 같은 경우에서 90이 두 번 쓰여 180을 만들 수 있다고 체크해 놨는데 실제로는 만들 수 없는 그런 상황이 생길 수 있다.

 

어쨌든 이런 중복 사용으로 인해 잘못된 결과가 체크되는 상황을 방지하려면? 반대로 탐색을 진행하면 된다.

 

for (auto weight : weights) {
    for (int i = n / 2; i > 0; i--) {
        for (int j = weight; j <= weight_sum; j++) {
            if (dp[i - 1][j - weight]) {
                dp[i][j] = 1;
            }
        }
    }
}

 

이렇게 진행하면

 

1	0	0	0	0
0	0	0	0	0
0	0	0	0	0

 

반대로 아래에서부터 탐색이 이루어진다 생각하면 weight = 1에서 dp [i - 1][j - weight] = 1인 경우는  dp [0][0]인 경우밖에 없고 그러면

 

1	0	0	0	0
0	1	0	0	0
0	0	0	0	0

 

이 된다. 순방향으로 탐색했을 때와 다른 점은 이미 갱신된 정보에 영향을 받아 중복 무게가 추가되었던 상황(dp [1][1] 때문에 dp [2][2]가 갱신된 경우]이 발생하지 않았다는 점이다. 실제로 역방향 탐색 결과표에서는 dp [2][2]의 시점에서 dp [1][1]은 0이었기 때문에 영향을 받지 않게 되었다.

 

이런 식으로 모든 사람 수의 경우와 모든 무게의 경우의 수에 대해 dp 테이블을 완성하면 다음과 같다.

 

1	0	0	0	0	0	0	0	0	0	0
0	1	1	1	0	1	0	0	0	0	0
0	0	0	1	1	1	1	1	0	0	0

 

이제 해야 하는 건? 사람 절반(n/2)인 시점 dp [n/2][?]에서 만들 수 있는 무게들에 대해 만약 한 팀의 무게가 w이면 다른 한 팀은 (총 무게 합-w) 이므로 두 무게의 차이의 절댓값은 abs((총 무게 합 - w) - w)이고 즉 abs(총 무게 합 - 2*w)에 대해 최솟값을 구해주면 된다.

 

int diff = weight_sum;
for (int i = 0; i <= weight_sum; i++) {
    if (dp[n / 2][i]) {
        if (diff > abs(weight_sum - 2 * i)) {
            diff = abs(weight_sum - 2 * i);
            ret1 = i;
        }
    }
}

ret2 = weight_sum - ret1;
if (ret1 > ret2) swap(ret1, ret2);
cout << ret1 << " " << ret2 << "\n";

 

사실상 여긴 구현이라 패스...

 

전체 코드

#include <bits/stdc++.h>
#define fastIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;

int n, w, weight_sum, ret1, ret2;
vector<int> weights;
int dp[54][45002];

void init() {
  cin >> n;

  weight_sum = 0;
  for (int i = 0; i < n; i++) {
    cin >> w;
    weights.push_back(w);
    weight_sum += w;
  }

  memset(dp, 0, sizeof(dp));
  dp[0][0] = 1;
}

void go() {
  for (auto weight : weights) {
    for (int i = n / 2; i > 0; i--) {
      for (int j = weight; j <= weight_sum; j++) {
        if (dp[i - 1][j - weight]) {
          dp[i][j] = 1;
        }
      }
    }
  }

  int diff = weight_sum;
  for (int i = 0; i <= weight_sum; i++) {
    if (dp[n / 2][i]) {
      if (diff > abs(weight_sum - 2 * i)) {
        diff = abs(weight_sum - 2 * i);
        ret1 = i;
      }
    }
  }

  ret2 = weight_sum - ret1;
  if (ret1 > ret2) swap(ret1, ret2);
  cout << ret1 << " " << ret2 << "\n";
}

int main() {
  fastIO;
  init();
  go();
  return 0;
}

 

하 진짜 디피는 풀 때마다 벽이 느껴지는 것 같다. 디피는 진짜 순방향/역방향, 상태 저장/ 상태값 저장 등 생각할 게 너무 많은 것 같다. 지금 배낭 문제로 분류된 디피 문제만 푸는데도 방식을 어떻게 엮을지 고민을 많이 했던 것 같다.

 

쉽지 않구만...