https://www.acmicpc.net/problem/14889
문제 해결 과정
착안
총 $N$ 명의 인원을 $(N / 2)$ 명씩 두 팀으로 나누는 모든 방법에 대하여, 능력치 값을 계산해보고 능력치 차이의 최솟값을 구하고자 하였다. 이때 팀 이름에 관계 없이 점수 차이만 계산하면 되므로, 중복하여 계산할 필요 없이 가장 처음 번호의 인원(1번 사람)은 반드시 첫 번째 팀에 포함된다고 가정할 수 있다(예를 들면 1번 사람이 속한 팀을 무조건 스타트 팀이라고 가정하는 것과 같음).
한편, 첫 번째 팀에 $(N / 2)$ 명의 멤버가 배정되면 나머지 인원은 자동적으로 두 번째 팀에 속하므로 이를 활용하고자 하였고, 백트래킹(backtracking, 퇴각검색) 알고리즘을 통해 다른 경우의 $(N / 2)$ 명으로 팀이 구성되는 경우에 대해서도 모두 능력치 차이값을 계산하여 문제를 해결하고자 하였다.
구현
앞에서 언급한 것과 같이, 0번 인덱스를 1번 팀에 배정하고 이후는 순차적으로 $(N / 2)$ 명이 될 때까지 1번 팀으로 멤버를 배정하여 $(N / 2)$ 명이 되면 능력치 차이값을 계산한 다음 백트래킹을 통해 다른 경우에 대해서도 계산하였다.
다른 분의 코드를 참고하니 두 팀으로 나누는 방식을 더 간편하게 구한 것 같은데, 해당 코드의 원리가 아직 잘 이해되지 않아서 추가적으로 공부해봐야 할 것 같다.
[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~
더보기
#include <iostream>
#include <vector>
using namespace std;
int N;
int S[20][20];
int Min = 2147483647;
int TeamScore(vector<int>& team)
{
int sum = 0;
for (int i : team)
for (int j : team)
sum += S[i][j];
return sum;
}
void Select(vector<int>& team, int n)
{
if (n < N || !Min)
{
team.push_back(n);
if ((int)team.size() == N / 2)
{
vector<int> team2;
int idx = 0;
for (int i = 0; i < N; i++)
{
if (team[idx] == i)
{
if (idx < N / 2 - 1)
idx++;
continue;
}
team2.push_back(i);
}
int diff = abs(TeamScore(team) - TeamScore(team2));
if (Min > diff)
Min = diff;
return;
}
for (int i = n + 1; i < N; i++)
{
Select(team, i);
team.pop_back();
}
}
}
int main()
{
ios::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 >> S[i][j];
vector<int> Team;
Select(Team, 0);
cout << Min << "\n";
return 0;
}
실행 결과
'C++ 코딩 문제 풀이 > 백준' 카테고리의 다른 글
[Baekjoon] 10866번: 덱 (0) | 2023.07.02 |
---|---|
[Baekjoon] 4134번: 다음 소수 (0) | 2023.07.02 |
[Baekjoon] 2630번: 색종이 만들기 (0) | 2023.06.29 |
[Baekjoon] 2805번: 나무 자르기 (0) | 2023.06.27 |
[Baekjoon] 1654번: 랜선 자르기 (0) | 2023.06.27 |
댓글