[BOJ] 백준 16132. 그룹 나누기 (Subset) (Gold III)

문제는 아래와 같다.

https://www.acmicpc.net/problem/16132

16132번: 그룹 나누기 (Subset)

맨 처음에 N=28일 때 답이 150만으로 나와서 짜증났던 문제이다.

주의할 점에 이어서 써보겠다.

---

의식의 흐름

N<=50이므로 TLE가 날 확률은 적다고 생각했다. 

그리고 조합론 느낌이 풀풀 나서 dp로 접근해보았다. 역시나 dp가 맞았는데,

사실 난 맨 처음엔 3차원 dp로 접근하였다.

 

먼저 N까지의 합 N*(N+1)/2 가 홀수일 경우, 두 팀의 합이 같을 수 없으므로 0을 출력해준다.

 

dp[cur][n][cnt]: cur번째 값 탐색, 현재까지의 합 n, 현재까지 포함된 개수 cnt.

만약 N=7일 때 답이 잘 나오지만, N=28의 답이 150만 정도로 나온다면,

팀을 14명/14명으로 나눌 때 값이 중복돼서 들어가기 때문이다.

 

따라서 cnt가 정확히 N/2일 때 dp값을 또 계산하여 빼주도록 하였다.

답이 int범위를 넘어감에 주의하자.

이렇게 하면 24ms가 나온다. (엄청 느린거다)

 

http://boj.kr/001766dc94984f38a41bd2e1010b592a (dp 3차원 배열, 24ms)

공유 소스 보기

 

그런데 생각해보면, 어차피 서로 중복되는 팀의 경우가 모든 경우에서 2가지이다.

예를 들어 N=7일 때, 1 6 7/2 3 4 5 와 같이 나눌 경우, 어차피 두 번 다 포함돼서 들어가기 때문이다.

따라서 dp를 위 코드처럼 두 번 할 필요 없이, 중복되지 않게 dp를 구해주거나, 아니면 모든 값을 다 구한 후 2로 나눠주면 된다. 따라서 dp를 2차원 배열로 줄일 수 있다. 개수(cnt)가 의미 없어지기 때문이다.

 

나는 중복되지 않게 dp를 구하는 방법을 선택했다.

N순위의 사람을 보유하고 있는 팀일 경우 return 0을 시켜버린 것인데,

잘 생각해보면 두 팀으로 나눌 경우, 한 팀은 무조건 N순위의 사람을 보유하고 있기 때문에 무조건 중복되는 경우를 배제할 수 있다.

---

코드

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int MAX = 51;
ll N, S, d[MAX][638], tmp;
ll dp(int cur, int n) {
	if (cur > N || n > S)
		return 0;
	if (n == S)
		return 1;
	ll& ret = d[cur][n];
	if (ret != -1)
		return ret;
	ret = 0;
	ret = dp(cur + 1, n) + dp(cur + 1, n + cur);
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	S = N * (N + 1) / 2;
	if (S % 2) {
		cout << 0 << "\n";
		return 0;
	}
	S /= 2;
	memset(d, -1, sizeof(d));
	cout << dp(1, 0) << "\n";
}