풀이까지 시간이 많이 걸린 문제다. 문제를 잘못 이해하고 접근한 것이 원인이었다.
알고리즘은 다음과 같이 진행된다.
먼저 N명을 입력받고 N*N 배열에 능력치를 입력받는다.
입력받은 N명 중 N/2명으로 팀을 나누는 모든 조합(단, 순서만 다른 조합은 제외)을 구한다.
조합에 속한 원소를 A팀 속하지 않은 원소를 B팀으로 나눠 각 팀의 능력치를 계산하고 A팀과 B팀의 능력치 차이를 구한다음 최솟값을 갱신해주면 원하는 출력을 얻을 수 있다.
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
const int INF = 987654321;
vector<vector<int>> member;
vector<int> picked;
vector<bool> visited;
int memNum;
int bestBalance = INF;
int min(int a, int b) { return a < b ? a : b; }
void Solution(int start, int toPick)
{
if (toPick == memNum / 2)
{
int Ateam = 0, Bteam = 0;
for (int i = 0; i < toPick; i++) // A팀
for (int j = 0; j < toPick; j++)
Ateam += member[picked[i]][picked[j]];
for(int i=0; i< memNum; i++) // B팀
for (int j = 0; j < memNum; j++)
{
if (visited[i] == true || visited[j] == true) continue;
Bteam += member[i][j];
}
int balance = abs(Ateam - Bteam);
bestBalance = min(bestBalance, balance);
return;
}
for (int i = start; i < memNum; i++)
{
picked.push_back(i);
visited[i] = true;
Solution(i+1, toPick + 1);
picked.pop_back();
visited[i] = false;
}
}
int main(void)
{
cin >> memNum;
for (int i = 0; i < memNum; i++)
{
vector<int> temp;
for (int j = 0; j < memNum; j++)
{
int n;
cin >> n;
temp.push_back(n);
}
visited.push_back(false);
member.push_back(temp);
temp.clear();
}
Solution(0,0);
cout << bestBalance << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
알고리즘 200일 프로젝트 - 9day
내일도 열심히!
'알고리즘 > BOJ' 카테고리의 다른 글
백준 15686번: 치킨 배달 (C++) (0) | 2020.04.15 |
---|---|
백준 14500번: 테트로미노 (C++) (0) | 2020.04.15 |
백준 1018번: 체스판 다시 칠하기 (0) | 2020.04.13 |
백준 1182번: 부분수열의 합 (0) | 2020.04.13 |
백준 1966번: 프린터 큐 (0) | 2020.04.13 |