ddongstudy
스타트와 링크 본문
문제
오늘은 스타트 링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
BOJ를 운영하는 회사답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
N=4이고, S가 아래와 같은 경우를 살펴보자.
| i/j | 1 | 2 | 3 | 4 |
| 1 | 1 | 2 | 3 | |
| 2 | 4 | 5 | 6 | |
| 3 | 7 | 1 | 2 | |
| 4 | 3 | 4 | 5 |
예를 들어, 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이 되고 이 값이 최소이다.
입력
첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
예제 입력 및 출력
입력
8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0
출력
1
소스 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int S[21][21]; //시너지 표
int N; //인원수
vector<int> start;
int getMinimum(int player, int num);
int getSynergy(vector<int> list);
vector<int> makeLink();
int main(void) {
//입력받기
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++)
cin >> S[i][j];
}
cout << getMinimum(0, 0);
}
int getMinimum(int player, int num) {
int balance = 2147483647;
int s_synergy, l_synergy; //각 그룹의 시너지
//재귀 탈출 조건 - 그룹에 선수가 다 참
if (num == N / 2) {
//start멤버를 다 지정했으면 나머지 멤버를 link멤버로 만들고 시너지를 구함
l_synergy = getSynergy(makeLink()); //link시너지
s_synergy = getSynergy(start); //start시너지
//시너지 차이를 구하여 반환
if (l_synergy > s_synergy)
return l_synergy - s_synergy;
else
return s_synergy - l_synergy;
}
//남은인원중 한명 추가
for (int i = player+1; i <= N; i++) {
start.push_back(i); //start 그룹에 추가
//재귀 함수 반환값과 현재 시너지 차이값 비교하여 최소값을 저장
balance = min(balance, getMinimum(i, num + 1));
start.pop_back(); //다시 그룹에서 뺌
}
return balance;
}
//그룹의 시너지를 계산하는 함수
int getSynergy(vector<int> list) {
int sum = 0;
for (int i = 0; i < list.size() ; i++) {
for (int j = 0; j < list.size(); j++)
sum += S[list.at(i)][list.at(j)];
}
return sum;
}
//Link그룹 만드는 함수
vector<int> makeLink() {
vector<int> link;
bool flag;
//1번~N번까지 순회
for (int i = 1; i <= N; i++) {
flag = true;
for (int j = 0; j < start.size(); j++) {
//i가 start그룹에 있는 선수이면 제외
if (i == start.at(j)) {
flag = false;
break;
}
}
//start멤버가 아니면 link멤버로 추가
if (flag == true)
link.push_back(i);
}
return link;
}
문제 풀이
1. 문제 해결 방법
-
완전 탐색의 방법을 이용하여 start그룹을 만들 수 있는 모든 경우의 수를 구한다.
-
start그룹의 인원이 전체 인원/2 만큼 채워지면 전체 인원에서 start그룹이 아닌 인원을 찾아 link인원으로 배정한다.
-
각 그룹의 시너지를 계산하여 차이를 반환하여 최솟값을 계속 비교하여 저장한다.
-
ex) 인원이 6명이 있는 경우 완전 탐색의 모든 경우는 다음과 같다.
2. 재귀 함수 탈출 조건
-
전체 인원이 N일 때 인자로 전달받은 start그룹의 인원이 N/2가 되면 각 그룹의 시너지 차이를 계산하여 반환한다.
-
반환된 시너지 차이 값을 현재 최솟값과 비교하여 더 작은 값으로 최솟값을 재설정해준다.
