https://www.acmicpc.net/problem/14889
문제
> 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다.
> 축구는 평일 오후에 하고 의무 참석도 아니다.
> 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다.
> 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
> BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다.
> 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다.
> 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다.
> Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
> N=4이고, S가 아래와 같은 경우를 살펴보자.
> 예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.
스타트 팀: S12 + S21 = 1 + 4 = 5
링크 팀: S34 + S43 = 2 + 5 = 7
> 1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.
스타트 팀: S13 + S31 = 2 + 7 = 9
링크 팀: S24 + S42 = 6 + 4 = 10
> 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다.
> 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면
스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.접근
해야할 기능은 3가지다.
1. 팀뽑기
2. 팀원에 따라 점수 계산(뒤집어서도)
3. 나온 점수를 각각의 경우마다 min연산으로 비교누적
팀뽑기는 0부터 입력받은 N까지 한명 뽑고 재귀로 동일한 선수를 뽑을 수 없으므로 뽑은 선수보다 큰 선수(1번선수 뽑았으면 2,3,4..선수)를 뽑기위해 현재 뽑은선수의 인덱스 +1과, 팀원의 수를 넣어 준다. 그래야 재귀탈출조건으로 팀원의 수가 N/2일 때, 로 점수 계산을 할 수 있다.
재귀로 해주면 알아서 N=6을 예로들면 012,013,014,015,023,024,025,034,035,045이렇게 된다.
자동으로 012, 021같이 같은 경우를 걸러줄 수 있다.
팀원에 따라 점수 계산은 이렇게 팀을 뽑았으면 이중 반복으로 i가 0~N-1, j가 i+1~N까지로 동일선수 경우, 순서바뀐 동일 경우를 걸러줄 수 있다.
i와 j에 대해 둘다 스타트팀인경우 스타트팀 점수에 ij, ji 두가지의 점수를 누적해준다. 반대로 둘다 링크팀이면 링크점수에 누적한다. 팀원을 부울형으로 받아 스타트팀이면 true, 링크팀이면 false로 줘서 이를 통해 구별해줄 수 있다.
계산이 끝나고 나면 나온 스타트팀과 링크팀의 점수를빼준다. 근데 둘중에 큰수가 뒤에오면 음수가 와 제대로된 결과가 안나올 수 있으므로 큰수를 선별해 계산 순서를 달리할 수 있지만 그냥 둘의 차를 절댓값(abs)처리해준다. 이 값과 Min값으로 준 최악의 점수 차이값과 비교한다. 팀원이 N/2명이 채워져 이 계산이 실행 될 때마다 Min값이 갱신되고 결국 다 돌면 제일 작은 값이 남아있을 것이다.
문제해결
> 점수차의 최악값 (각각 10명씩 전부 100점일 때 뒤집은거 까지 더해서 2000이 최대, 전부 1점일 때 20점이 최소 이므로 둘이 뺴면 1980이 최악의 점수다.)을 1980으로 정의해준다.
> 팀원을 담을 team 부울형 벡터르 선언하고 스타트팀은 true, 링크팀은 false로 가진 인덱스(선수번호)를 팀원으로 가진다.
> 각 선수 조합별 점수를 담을 score벡터와 팀뽑기, 점수 계산, 팀 점수 차의 최소값 계산을 해줄 Team메소드를 정의해준다.
> 인자로 팀원의 번호와 팀원의 수를 가진다.
재귀의 탈출 조건으로 팀원이 N/2명을 만족했을 때 점수계산을 해주고 나온 두 팀의 점수로 최소값을 갱신하고 탈출한다.
> N/2명이 아니면 이를 채워야하므로 인자로 들어온 number부터 반복문을 돌려 팀원을 고른다.
(number 이전의 수는 이미 앞에서 골랐다는 뜻이고, 01, 10같은 중복을 걸러주기 위해서다.)
> 재귀로 이번에 고른 팀원의 번호 +1과 팀원이 한명 늘어났기에 +1해준 값을 넘긴다. 그럼 다음 재귀에서 팀원이 부족하면 또 재우고 재귀할것이고 아니면 점수 계산이 될것이다.
점수 계산이 끝나고 다시 돌아오면 이제 골랐던 선수를 다시 빼줘야 새로운 팀원 조합을 재귀로 만들어 낼 수 있다. 이를 처리해준다.
> main함수에서 팀원의 조합별 점수를 입력받고 Team메소드에 0번 선수부터, 팀원은 0명이니까 0,0을 넣어 돌린다.
> 위 과정을 끝내고 나온 Min(점수 차이의 최소값)을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int Min = 1980;
int N;
vector<bool> team;
vector<vector<int>> score;
void Team(int number, int memcnt)
{
if (memcnt == N / 2)
{
int startsum = 0, linksum = 0;
for (int i = 0; i < N-1; i++)
{
for (int j = i + 1; j < N; j++)
{
if (team[i] && team[j])
{
startsum += score[i][j];
startsum += score[j][i];
}
else if (!team[i] && !team[j])
{
linksum += score[i][j];
linksum += score[j][i];
}
}
}
Min = min(Min, abs(startsum - linksum));
return;
}
for (int i = number; i < N; i++)
{
team[i] = true;
Team(i + 1, memcnt + 1);
team[i] = false;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
team.assign(N, false);
score.resize(N, vector<int>(N));
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> score[i][j];
}
}
Team(0, 0);
cout << Min << '\n';
}
후기
팀 뽑는건 예전에 N과 M이라는 문제에서 했던 로직을 적용해봤다. 그 땐 뽑아서 팀 벡터에 뽑힌애들 넣어놓고 나중에 벡터에서 뽑아서 계산하고 했었는데 굳이 그럴 필요없이 그냥 팀에 누가 있나만 알면 되니 부울로 처리해줬다. 불필요한 과정이 줄어들었다.
그리고 반복문을 0~n, 0~n으로 주고 i==j 넘기면서 그냥 순서만 다른 중복경우를 따로 처리안해줄 수 있었지만
반복문이 길어지면 안좋을거같아서 반복문을 줄이고 겹치는걸 처리헀다.
해야할 구조들의 구상은 잘 했지만 이 구조들을 연결하고 조합하는게 조금 어려웠다.
그래도 구조를 생각해낸다는거에서 좀 성장했다고 느꼈다.
