백준 14889 - 스타트와 링크(C++)

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

14889번: 스타트와 링크

삼성 SW 역량테스트 기출문제입니다.

조합을 사용하면 풀 수 있는 문제였습니다.

문제 조건

출력 예시

N개의 수가 입력되었을때, N/2인 팀을 2개 만들어서 두 팀의 능력치 차의 최솟값을 구하는 문제입니다.

6명이 있다고 했을때, 팀이 (1, 2, 3) 과 (4, 5, 6)으로 나누어졌다고 가정하겠습니다.

이때 (1, 2, 3)이나 (3, 2, 1)이나 (2, 1, 3)이나 모두 같은 경우입니다.

마찬가지로 (4, 5, 6)이나 (6, 5, 4)나 (5, 4, 6)이나 모두 같은 경우입니다.

 

따라서 N/2 명이 나올 수 있는 경우를 모두 찾은뒤, 남은 인원이 반대 팀이 되어 값을 구하면 된다는 의미입니다.

예를 들어 (1, 2, 3)이 선택되었을때, (4, 5, 6)이 반대팀이 되는 것입니다.

 

1. 조합 구현하기

void dfs_team(int x, int cnt) {
	int first_point = 0, second_point = 0;
	if (cnt == N/2) {
		for (int i = 1; i <= N; i++) {
			if (check[i] == 0) second_team.push_back(i);
		}
		for (int i = 0; i < first_team.size(); i++) {
			for (int j = 0; j < first_team.size(); j++) {
				first_point += map[first_team[i]][first_team[j]];
			}
		}
		for (int i = 0; i < second_team.size(); i++) {
			for (int j = 0; j < second_team.size(); j++) {
				second_point += map[second_team[i]][second_team[j]];
			}
		}
		mini = min(mini, abs(first_point - second_point));
		second_team.clear();
	}
	else {
		for (int i = x + 1; i <= N; i++) {
			if (check[i] == 0) {
				check[i] = 1;
				first_team.push_back(i);
				dfs_team(i, cnt + 1);
				first_team.pop_back();
				check[i] = 0;
			}
		}
	}
}

먼저 팀 인원수를 N/2 명을 선택해야됩니다. 따라서 선택된 수가 N/2 가 된 경우, 팀의 능력치를 비교해줍니다.

N/2 명보다 선택이 덜되었을 경우, check배열을 통해 이전에 선택되지 않은 학생을 선택해줍니다.

따라서 (1, 2, 3) -> (1, 2, 4) -> (1, 2, 5) -> (1, 2, 6) -> (1, 3, 4) ..... -> (4, 5, 6)까지 선택됩니다. (N이 6일때)

선택되지 않은 사람은 반대팀으로 저장해준뒤, 서로의 능력치를 구해 빼줍니다.

 

 

문제 접근 방법

1. 팀을 N/2명 정한다.

2. 두 팀의 능력치를 비교한다.

3. 해당 과정을 모든 조합이 나올때까지 반복한다.

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
#include <cstring>

using namespace std;

int N;
int map[21][21];
int check[21];
vector<int> first_team, second_team;
int mini = 987654321;

void dfs_team(int x, int cnt) {
	int first_point = 0, second_point = 0;
	if (cnt == N/2) {
		for (int i = 1; i <= N; i++) {
			if (check[i] == 0) second_team.push_back(i);
		}
		for (int i = 0; i < first_team.size(); i++) {
			for (int j = 0; j < first_team.size(); j++) {
				first_point += map[first_team[i]][first_team[j]];
			}
		}
		for (int i = 0; i < second_team.size(); i++) {
			for (int j = 0; j < second_team.size(); j++) {
				second_point += map[second_team[i]][second_team[j]];
			}
		}
		mini = min(mini, abs(first_point - second_point));
		second_team.clear();
	}
	else {
		for (int i = x + 1; i <= N; i++) {
			if (check[i] == 0) {
				check[i] = 1;
				first_team.push_back(i);
				dfs_team(i, cnt + 1);
				first_team.pop_back();
				check[i] = 0;
			}
		}
	}
}

void solve() {
	dfs_team(0, 0);
	cout << mini;
}

int main()
{
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> map[i][j];
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!