[백준 14889번] 스타트와 링크 (조합)

삼성 SW 역량테스트 기출문제인 백준 사이트의 14889번 문제 스타트와 링크를 풀이해보겠습니다. 이 문제는 조합을 사용하는 단일 알고리즘 문제입니다. 난이도 수준이 매우 낮은 문제이기 때문에 꼭 빠르게 맞춰야 하는 문제입니다. 다른 조합 문제에 비해 응용하는 부분도 적습니다.

 

2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 14888번] 연산자 끼워넣기 (순열)

2021.04.08 - [알고리즘/SW역량테스트 기출문제] - [백준 15686번] 치킨배달 (조합)

2021.04.14 - [알고리즘/SW역량테스트 기출문제] - [백준 14889번] 스타트와 링크 (조합)

2021.04.18 - [알고리즘/SW역량테스트 기출문제] - [백준 15683번] 감시 (조합)

2021.04.20 - [알고리즘/SW역량테스트 기출문제] - [백준 14501번] 퇴사 (조합)

 

안녕하세요. 지칸입니다.

오늘 포스팅할 문제는 14889번 스타트와 링크 문제로 기출 된 지 좀 지난 문제입니다. 조합 알고리즘의 기본 연습 개념으로 가져와봤습니다. 요즘 난이도를 생각하면 이 정도 난이도는 쉽게 풀이할 수 있어야 합니다.

 

1) 문제 이해

2) 구조 잡기

 

 

저의 결론) 기본적인 조합 문제입니다... 이하 생략

---

1) 문제 이해

문제 출처 : www.acmicpc.net/problem/14889

 

문제)

오늘은 스타트 링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 

 

-> 문제 해석

NxN 2차원 배열 사용

N명중 N/2명 선택해서 한 팀, 나머지는 자동 다른 팀, 조합 문제

팀 능력치 계산 = 해당 팀의 모든 쌍의 합 -> 2중 for문, Sii는 0이기 때문에 무시하고 전체 합하면 됨

 

입력)

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij이다.ij Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

-> 입력 해석

MAX_N = 20

 

출력)

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

-> 출력 해석

N명 중 N/2명 선택하는 모든 경우의 수를 차례대로 검색하며 글로벌 최솟값을 비교 저장

---

2) 구조 잡기

이전 문제들과 마찬가지로 동일하게 시작합니다.

2019.04.25 - [알고리즘/SW역량테스트] - (1장-1) 역량 테스트 기본 템플릿 준비

 

2-1) 초기 세팅

2차원 S배열 정보를 저장하는 기본 구조를 만들어줍니다. 진짜 삼성 SW 역량테스트에서는 테스트 케이스로 반복하기 때문에 약간의 차이는 존재합니다. 꼭 인식하세요.

#include <iostream>
using namespace std;
#define MAX_N 20
#define MAX_C 123456789
int N;
int S[MAX_N][MAX_N] = { 0, };
int sol = MAX_C;

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> S[i][j];
		}
	}
	// N명 중 N/2명 선택, 조합 합수 넣기
	cout << sol;
	return 0;
}

 

2-2) 조합 구현하기

N명 중 N/2명을 선택하는 조합입니다. 조합의 경우 항상 동일한 방식으로 코딩하시면 됩니다.

2021.04.01 - [알고리즘/SW역량테스트] - (4장-2) 조합(Combination) 알고리즘이란?

#include <vector>
vector<int> flag;
vector<int> selectA;
vector<int> arr;

void comb(int n, int r) {
	if (n == r) {
		for (int i = 0; i < n; i++) {
			flag[i] = 1;
		}
		for (int i = 0; i < arr.size(); i++) {
			if (flag[i] == 1) selectA.push_back(arr[i]); 
		}
		operation();  // N/2명 선택시 동작
		selectA.clear(); 
		for (int i = 0; i < n; i++) {
			flag[i] = 0;
		}
		return;
	}
	if (r == 1) {
		for (int i = 0; i < n; i++) {
			flag[i] = 1;
			for (int j = 0; j < arr.size(); j++) {
				if (flag[j] == 1) selectA.push_back(arr[j]); 
			}
			operation();  
			selectA.clear(); 
			flag[i] = 0;
		}
		return;
	}
	flag[n - 1] = 1;
	comb(n - 1, r - 1);
	flag[n - 1] = 0;
	comb(n - 1, r);
}

int main() {
	// .. 기존 코드 생략 ..
	for (int i = 0; i < N; i++) {
		flag.push_back(0);
		arr.push_back(i); // 전체 후보
	}
    
	comb(N, (int)(N/2)); // N명 중 N/2 선택
	cout << sol;
	return 0;
}

기존 조합 알고리즘과 달라진 점은 배열의 이름만 변화했습니다. 그 외 설명은 조합 알고리즘 포스팅을 확인해 주세요.

 

2-3) 팀의 능력치 계산 구현하기

void operation() {
	vector<int> selectB; 
	bool eq = false;
	for (int i = 0; i < N; i++) {
		eq = false;
		for (int j = 0; j < selectA.size(); j++) {
			if (arr[i] == selectA[j]) {
				eq = true;
				break;
			}
		}
		if (eq == false) selectB.push_back(arr[i]);
	} // B팀을 만들어 주는 동작, 전체에서 A팀 여부를 전부 체크...

	int Sa = 0;
	int Sb = 0;
	for (int i = 0; i < selectA.size(); i++) {// A,B 두팀의 크기는 같음
		for (int j = 0; j < selectA.size(); j++) {
			Sa += S[selectA[i]][selectA[j]]; // i==j일때는 0이니까 무시하고 전부 합
			Sb += S[selectB[i]][selectB[j]];
		}
	}
	int min = 0;
	if (Sa > Sb) {
		min = Sa - Sb; // 두 팀의 차이 계산
	}
	else {
		min = Sb - Sa; 
	}

	if (sol > min) // 모든 조합의 경우의 수를 찾아가며 최솟값 찾기
		sol = min;
}

조합 과정에서 N명중 N/2명을 A팀으로 선정했습니다. 자연스럽게 남은 N/2명이 B팀으로 결정되는데 이걸 계산하기 위해 N명 전체를 A팀 멤버와 비교하면서 찾아냈습니다. 좀 무식하게 계산하더라고 MAX_N 20이기 때문에 계산량이 많지 않습니다.

 

A팀과 B팀 각각 팀 능력치를 계산하면 되는데 둘의 팀원 수는 같습니다. 그리고 i==j일 때 Sij=0이기 때문에 이중 반복문으로 전부 더해주면 간단히 팀 능력치를 계산할 수 있습니다.

 

이후, 모든 조합의 최솟값을 찾기 위해 글로벌 변수 sol와 min값을 비교합니다.