14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
풀이까지 시간이 많이 걸린 문제다. 문제를 잘못 이해하고 접근한 것이 원인이었다.
알고리즘은 다음과 같이 진행된다.
먼저 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 |