이번에는 백준 14889번 스타트와 링크 문제를 풀어보았습니다.
N명의 사람을 정확히 절반씩 두 팀으로 나눈 뒤, 두 팀의 능력치 차이를 최소화해야 합니다.
팀을 나누는 모든 경우를 확인해야 하므로 조합 또는 비트마스킹을 이용한 완전탐색으로 해결할 수 있습니다.
문제 설명
N명의 사람을 다음 두 팀으로 나누어야 합니다.
- 스타트 팀
- 링크 팀
각 팀은 정확히 N / 2명으로 구성되어야 합니다.
두 사람이 같은 팀에 속하면 능력치 Sij가 팀 능력치에 추가됩니다.
Sij와 Sji는 서로 다를 수 있으므로, 두 사람이 같은 팀에 속한 경우 두 값이 모두 포함됩니다.
모든 팀 구성 중에서 스타트 팀과 링크 팀의 능력치 차이가 최소가 되는 값을 구하는 문제입니다.
풀이 아이디어
N은 최대 20이므로 가능한 팀 구성을 모두 확인하는 완전탐색을 사용할 수 있습니다.
팀을 정확히 절반으로 나눈 뒤, 각 팀에 속한 선수들의 능력치를 모두 더합니다.
이후 두 팀 능력치의 차이를 계산하여 최솟값을 갱신합니다.
V1에서는 재귀 조합으로 한 팀의 선수들을 선택한 뒤, 해당 팀 정보를 비트로 변환하여 능력치를 계산하였습니다.
V2에서는 모든 비트를 순회하면서 켜진 비트의 개수가 N / 2인 경우만 팀 구성으로 사용하였습니다.
V1 코드
#include <bits/stdc++.h>
using namespace std;
int N;
int input_arr[20][20];
int ret = INT_MAX;
int check(int team_bit) {
int a_sum=0;
int b_sum=0;
for (int i=0; i<N; i++) {
if (team_bit & (1<<i)) {
for (int j=0; j<N; j++) {
if(team_bit & (1<<j)) a_sum += input_arr[i][j];
}
} else {
for (int j=0; j<N; j++) {
if(!(team_bit & (1<<j))) b_sum += input_arr[i][j];
}
}
}
return abs(b_sum - a_sum);
}
void combi(int st, vector<int> b) {
if (b.size() == N/2) {
int team_bit = 0;
for (int num : b) {
team_bit |= (1 << num);
}
int diff = check(team_bit);
ret = min(ret, diff);
return;
}
for (int i=st+1; i<N; i++) {
b.push_back(i);
combi(i,b);
b.pop_back();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
cin >> input_arr[i][j];
}
}
vector<int> b;
combi(-1,b);
cout << ret;
return 0;
}V2 코드
#include <bits/stdc++.h>
using namespace std;
int N;
int input_arr[20][20];
int ret = INT_MAX;
int check(vector<int> a, vector<int> b) {
int a_sum=0;
int b_sum=0;
for (int i=0; i<N/2; i++) {
for (int j=0; j<N/2; j++) {
a_sum += input_arr[a[i]][a[j]];
b_sum += input_arr[b[i]][b[j]];
}
}
return abs(b_sum - a_sum);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
cin >> input_arr[i][j];
}
}
for (int i=0; i<(1<<N); i++) {
if(__builtin_popcount(i) != N / 2) continue;
vector<int> a,b;
for (int j=0; j<N; j++) {
if (i & (1<<j)) a.push_back(j);
else b.push_back(j);
}
ret = min(ret, check(a,b));
}
cout << ret;
return 0;
}풀이 흐름
-
사람들의 능력치 정보를 입력받습니다.
-
N명 중 정확히
N / 2명을 한 팀으로 선택합니다. -
선택된 사람들은 A팀, 선택되지 않은 사람들은 B팀으로 구분합니다.
-
각 팀 내부의 모든
Sij값을 더해 팀 능력치를 구합니다. -
두 팀 능력치 차이의 절댓값을 계산합니다.
-
현재까지 구한 최솟값과 비교하여 정답을 갱신합니다.
-
가능한 모든 팀 구성을 확인한 뒤 최솟값을 출력합니다.
구현 포인트
1. V1의 조합 생성
V1에서는 재귀 함수 combi()를 사용하여 N명 중 N / 2명을 선택하였습니다.
void combi(int st, vector<int> b)st는 마지막으로 선택한 사람의 인덱스이고, b에는 현재까지 선택한 사람들의 번호가 저장됩니다.
for (int i=st+1; i<N; i++) {
b.push_back(i);
combi(i,b);
b.pop_back();
}현재 사람을 선택한 뒤 재귀 호출하고, 호출이 끝나면 다시 제거합니다.
이 과정은 DFS와 백트래킹을 이용해 조합을 만드는 방식입니다.
2. 팀 인원이 절반이 된 경우
if (b.size() == N/2)선택한 사람의 수가 N / 2명이 되면 하나의 팀 구성이 완성된 것입니다.
선택된 사람들을 비트로 표현하기 위해 team_bit를 사용합니다.
int team_bit = 0;
for (int num : b) {
team_bit |= (1 << num);
}선택된 사람의 위치에 해당하는 비트를 1로 설정합니다.
예를 들어 0번과 2번 사람이 선택되었다면 다음과 같이 표현할 수 있습니다.
0101비트가 1인 사람은 A팀, 0인 사람은 B팀으로 구분합니다.
3. 비트로 팀 구분하기
if (team_bit & (1<<i))i번째 비트가 켜져 있다면 i번 사람은 A팀에 속합니다.
if(team_bit & (1<<j))
a_sum += input_arr[i][j];i와 j가 모두 A팀에 속한다면 Sij를 A팀 능력치에 더합니다.
반대로 i번째 비트가 꺼져 있다면 B팀에 속합니다.
if(!(team_bit & (1<<j)))
b_sum += input_arr[i][j];i와 j가 모두 B팀에 속한 경우에만 B팀 능력치를 더합니다.
4. 능력치를 중복해서 더하는 이유
문제에서는 같은 팀에 속한 두 사람 i, j에 대해 다음 두 값이 모두 포함됩니다.
Sij + Sji코드에서는 모든 i, j 조합을 순회합니다.
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {따라서 input_arr[i][j]와 input_arr[j][i]가 각각 한 번씩 더해집니다.
Sii는 항상 0이므로 같은 사람을 확인하는 경우가 포함되어도 결과에는 영향을 주지 않습니다.
5. 두 팀 능력치 차이 계산
return abs(b_sum - a_sum);두 팀 중 어느 팀의 능력치가 더 클지 알 수 없으므로 절댓값을 사용합니다.
이 값을 현재까지의 최솟값과 비교합니다.
ret = min(ret, diff);모든 팀 구성을 확인한 뒤 ret에는 최소 능력치 차이가 저장됩니다.
6. V2의 비트마스킹 완전탐색
V2에서는 재귀 조합 함수 대신 모든 비트 상태를 직접 순회합니다.
for (int i=0; i<(1<<N); i++)N명의 각 사람은 두 가지 상태를 가질 수 있습니다.
- 비트가 1이면 A팀
- 비트가 0이면 B팀
따라서 전체 팀 구성은 2^N개입니다.
7. __builtin_popcount() 사용
모든 비트 상태가 두 팀의 인원을 절반으로 나누는 것은 아닙니다.
따라서 켜진 비트의 개수가 정확히 N / 2인 경우만 확인합니다.
if(__builtin_popcount(i) != N / 2) continue;__builtin_popcount(i)는 정수 i의 이진수 표현에서 1로 설정된 비트의 개수를 반환합니다.
예를 들어 다음 비트에는 1이 세 개 있습니다.
10110따라서 __builtin_popcount()의 반환값은 3입니다.
8. 비트를 두 팀의 벡터로 변환
vector<int> a,b;
for (int j=0; j<N; j++) {
if (i & (1<<j)) a.push_back(j);
else b.push_back(j);
}현재 비트에서 j번째 비트가 켜져 있으면 A팀에 추가합니다.
비트가 꺼져 있으면 B팀에 추가합니다.
앞에서 켜진 비트의 개수가 N / 2인지 확인했으므로 두 팀 모두 정확히 N / 2명으로 구성됩니다.
9. V2의 팀 능력치 계산
int check(vector<int> a, vector<int> b)두 팀의 선수 번호를 각각 벡터로 전달받습니다.
각 팀은 정확히 N / 2명이므로 이중 반복문을 사용하여 팀 내부의 모든 능력치를 더합니다.
for (int i=0; i<N/2; i++) {
for (int j=0; j<N/2; j++) {
a_sum += input_arr[a[i]][a[j]];
b_sum += input_arr[b[i]][b[j]];
}
}A팀에서는 a[i], a[j]에 해당하는 능력치를 더하고, B팀에서는 b[i], b[j]에 해당하는 능력치를 더합니다.
10. V1과 V2의 차이
V1은 재귀와 백트래킹을 이용해 필요한 조합만 생성합니다.
combi(-1,b);처음부터 정확히 N / 2명을 선택하는 경우만 만들기 때문에 팀 인원이 맞지 않는 상태는 생성하지 않습니다.
V2는 0부터 2^N - 1까지 모든 비트 상태를 확인한 뒤, __builtin_popcount()를 이용해 인원이 절반인 경우만 사용합니다.
if(__builtin_popcount(i) != N / 2) continue;따라서 두 코드 모두 가능한 팀 구성을 완전탐색하지만, 팀 구성을 생성하는 방식이 다릅니다.
- V1: 재귀 조합
- V2: 비트마스킹 완전탐색
11. 같은 팀 구성을 두 번 확인하는 경우
A팀과 B팀을 서로 바꾼 구성은 사실상 같은 팀 분할입니다.
예를 들어 다음 두 경우는 팀의 이름만 바뀐 동일한 구성입니다.
A팀: 1, 2 / B팀: 3, 4
A팀: 3, 4 / B팀: 1, 2두 경우 모두 능력치 차이의 절댓값은 같습니다.
현재 코드는 이러한 대칭인 경우를 모두 확인하지만, N이 최대 20이므로 제한 시간 내에 해결할 수 있습니다.
12. 시간복잡도
V1에서는 N명 중 N / 2명을 고르는 조합의 수만큼 탐색합니다.
각 팀 구성마다 check() 함수에서 N²개의 관계를 확인합니다.
따라서 시간복잡도는 다음과 같습니다.
O(C(N, N/2) × N²)V2에서는 2^N개의 비트 상태를 순회합니다.
각 상태에서 __builtin_popcount()를 확인하고, 유효한 팀 구성이라면 팀 능력치를 계산합니다.
따라서 전체 시간복잡도는 다음과 같이 볼 수 있습니다.
O(2^N × N²)N은 최대 20이므로 두 방식 모두 완전탐색으로 해결할 수 있습니다.
