[백준][삼성 SW 역량 테스트][Silver 3][C++] 14889 스타트와 링크

문제

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

14889번: 스타트와 링크

 

---

문제 풀이

접근 방식

스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 구하는 문제이다.

이 문제는 사람들을 두 팀으로 나눠 능력치를 계산하는 간단한 조합 문제였다.

 

우선 사람들의 능력치를 입력 받은 후, 팀을 나누기 위해 next_permutation을 사용해주었다.

인덱스를 0과 1로 나눠 팀을 나눠주었고, 각 팀의 능력치를 계산하여 능력치의 차이를 구해주었다.

구한 능력치의 차이를 answer과 비교하며 최솟값을 구해주었다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	// 입력
	int N;
	cin >> N;
	vector<vector<int> > v(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)	{
			cin >> v[i][j];
		}
	}

	// 조합
	vector<int> idx(N);
	for (int i = 0; i < N; i++)	{
		if (i < N / 2)
			idx[i] = 0;
		else
			idx[i] = 1;
	}

	int answer = 10000000;
	do {
		// 각 팀의 능력치 구하기
		int power1 = 0;
		int power2 = 0;
		vector<int> team1;
		vector<int> team2;
		for (int i = 0; i < N; i++) {
			if (idx[i] == 0)
				team1.push_back(i);
			else
				team2.push_back(i);
		}
		for (int a = 0; a < N / 2; a++) {
			for (int b = 0; b < N / 2; b++) {
				power1 += v[team1[a]][team1[b]];
				power2 += v[team2[a]][team2[b]];
			}
		}

		// 능력치 차이의 최솟값 구하기
		if (answer > abs(power1 - power2))
			answer = abs(power1 - power2);
		if (answer == 0) break;
	} while (next_permutation(idx.begin(), idx.end()));
	cout << answer;
}

실행 결과

실행 결과 : 통과 (88ms)