Min:D's Devlog

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

알고리즘/백준

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

Min:D 2020. 10. 1. 14:00

문제

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

 

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

 


문제 풀이

접근 방식

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

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

 

우선 사람들의 능력치를 입력 받은 후, 팀을 나누기 위해 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)

Comments