백준 14889번 스타트와 링크 (삼성 SW 역량테스트 기출문제)

문제 링크: https://www.acmicpc.net/problem/14889

사용한 알고리즘: Brute Force


 문제에서 N명의 사람을 주고, i,j번째 사람이 한 팀일 경우의 능력치를 입력으로 주고 있습니다. 특이한 점은 i,j 와 j,i의 능력치가 다릅니다. 문제에도 주어지지만 i,j가 한 팀이 된 경우, i,j 와 j,i의 능력치를 모두 팀 능력치에 더해주면 됩니다. 구하고자 하는 값은 두 팀을 만들었을 때 두 팀간의 능력치 차의 최소값입니다.

 기본적으로 N이 최대 20으로 주어졌기 때문에 Brute Force 를 쓰면 해결이 가능합니다.

 문제를 푸는 과정은 다음과 같습니다.

(1) Brute Force를 수행할 함수를 하나 만들어 주었습니다. 이때 이 함수는 1~N 사람을 모두 볼 것입니다. 또한 Stark와 Link라는 두 vector을 들고 갑니다.
i번째 사람을 함수로 돌릴때는 각각 Stark에 넣고 i+1번째 사람으로 넘어가고,
 Stark에 넣었던걸 도로 빼고 i번째 사람을 Link에 넣고 i+1번째 사람으로 넘어갑니다.
이때 Link에 i번째 사람을 넣을시, 앞서 Stark에 넣어놨던 i번째사람을 빼야 됨을 주의해주어야 됩니다.

(2) 함수를 돌리면서 Stark,Link 중 하나의 크기가 N/2가 되었을 경우, 즉 가득 찼을 경우 (두 팀은 모두 N/2명의 사람을 포함해야 합니다.) 남은 사람을 모두 반대 vector에 넣어주고 두 팀의 능력치를 계산후 구하고자 하는 두 팀간의 능력치 차이의 최소값을 최신화 해줍니다.

	#include <bits/stdc++.h>
	using namespace std;
	//Brute Force
	int N, arr[20][20];
	int ans = 987654321;
	vector<int> temp1,temp2;
	void Diff(vector<int> A, vector<int> B){
	int a = 0;
	int b = 0;
	for (int i = 0; i < N/2; ++i){
	for (int j = 0; j < N/2; ++j){
	a+=arr[A[i]][A[j]];
	b+=arr[B[i]][B[j]];
	}
	}
	ans = min(ans,abs(a-b));
	}
	void MakeAns(int idx, vector<int> Stark, vector<int> Link){
	// 남은사람 수 = 뽑아야 될 사람수 일때
	if(Stark.size()==N/2){
	for (int i = idx; i < N; ++i) Link.push_back(i);
	Diff(Stark,Link);
	return;
	}
	if(Link.size()==N/2){
	for (int i = idx; i < N; ++i) Stark.push_back(i);
	Diff(Stark,Link);
	return;
	}
	Stark.push_back(idx);
	MakeAns(idx+1,Stark,Link);
	Stark.pop_back();
	Link.push_back(idx);
	MakeAns(idx+1,Stark,Link);
	return;
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	cin >> arr[i][j];
	MakeAns(0,temp1,temp2);
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 14889.cpp hosted with ❤ by GitHub