[삼성코테기출문제] 스타트와 링크

스타트와 링크

문제

또 Brute Force… 완전탐색 으로 푸는 문제가 많은 것 같다. 처음에 문제 해석이 좀 잘못되서 엉뚱한 방향으로 풀다가 제대로 해석한 후 문제를 풀었다. 왠만한 조건은 다 맞춘것같은데 답이 나오질 않았다…. 문제는 재귀함수에 넘기는 매개변수를 잘못넣었었다… 완벽하다고 생각했는데 사소한 부분에서 나오는 실수… 너무 많은 것 같다. 내일이면 하반기 역량테스트인데 이런 실수는 꼭 하지말도록하자!

문제 풀이

N명의 선수들 중 2명씩 짝지었을때 시너지에 대한 정보가 주어지고 그 선수들을 스타트 팀과 링크 팀이 반반씩 나누어 가지는데 N/2 명중 2명을 뽑는 모든 경우의 시너지를 합하여 스타트 팀과 링크 팀의 차이가 최소인 경우를 구하는 문제이다.

입출력 조건

풀이 과정

1. 선수 쌍의 시너지를 나타내는 2차원 배열에서 N/2만큼 선택하여 true를 주고 나머지 N/2는 false를 주어 스타트 팀과 링크팀의 선수를 나눈다.
2. 팀을 나눈 후 각 팀의 한 쌍 시너지를 모두 구하여 s와 l에 더해준다.
3. 두 팀의 시너지 합의 차를 절대값으로 구하고 그 것이 최솟값인지 판단 후 다음 재귀함수로 넘어간다.
4. 재귀함수는 N명중 N/2명을 고르는 과정으로 해당 모든 과정에 대하여 위의 과정을 반복해준다. 이 재귀함수를 넘기는 과정에서 실수가 있었는데

  void Team(int j, int n) {
	if (n == N / 2) {
		Sky.clear();
		Link.clear();
		for (int i = 0; i < N; i++) 
			if (Player[i])Sky.ush_back(i);
			else Link.push_back(i);
		}
		Process();
		return;
	}
	for (int i = j+1; i < N; i++) {
		Player[i] = true;
		Team(i, n + 1);
		Player[i] = false;
	}
}

재귀로 넘어가는 부분에서 i를 넘겨받아야하는데 j를 넘겨받아서 계속 답이 안나왔었다. 진짜 사소한 실수인데 시간은 엄청 잡아먹었다…

#include<iostream>
#include<vector>
using namespace std;
const int MAX = 20;
int Res;
int a[MAX][MAX];
int N, Min = 1 << 30;
bool Player[MAX];
vector<int> Sky;
vector<int> Link;
int answer[2];
void Input() {
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> a[i][j];
}
void Process() {
	int s = 0;
	int l = 0;
	for (int i = 0; i < N/2; i++) {
		for (int j = i + 1; j < N/2; j++) {
			s += a[Sky[i]][Sky[j]] + a[Sky[j]][Sky[i]];
			l += a[Link[i]][Link[j]] + a[Link[j]][Link[i]];
		}
	}
	//int res = s > l ? s - l : l - s;
	Res= s > l ? s - l : l - s;
	//if (Min > res)Min = res;
	if (Min > Res)Min = Res;
}
void Team(int j, int n) {
	if (n == N / 2) {
		Sky.clear();
		Link.clear();
		for (int i = 0; i < N; i++) {
			if (Player[i])Sky.push_back(i);
			else Link.push_back(i);
		}
		Process();
		return;
	}
	for (int i = j+1; i < N; i++) {
		Player[i] = true;
		Team(i, n + 1);
		Player[i] = false;
	}
}

void Solution() {
	Input();
	for (int i = 0; i < N; i++) {
		Player[i] = true;
		Team(i, 1);
		Player[i] = false;
	}
	cout << Min << "\n";
}
int main() {
	freopen("11.in", "r", stdin);
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	Solution();
	return 0;
}