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

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

아이디어

나는 문제를 3가지 파트로 나눠서 풀었다.

1. 입력을 받는 부분

2. 팀을 짜는 부분

3. 짜여진 팀을 이용해서 점수를 계산하고 큐에 기록

 

입력을 받고, 짜여진 팀을 이용해 점수를 계산하는 것을 어렵지 않다. 이 문제의 핵심적인 부분은 팀을 짜는 부분이다. 그 부분은 아래와 같이 구현하였다. 

이 문제의 경우에는 사람이 스타트팀 혹은 링크팀이기 때문에 스타트팀에 절반을 배정하면 나머지는 자동으로 링크팀이 된다. 

//팀을 짜는 함수
//curteamsiz : 현재 팀에 몇 명이 들어왔는가
//before_end : 몇 번 사람까지 팀에 배치를 했는가
void maketeam(int curteamsiz, int before_end) {
    //팀 인원이 모두 찰 경우(전체 인원의 절반이 스타트팀으로 배치 완료)
	if (curteamsiz == n/2) {
        //팀 배치가 완료됐으니 스타트팀의 점수-링크 팀의 점수
		int save = calculate_start()-calculate_link();
		if (save < 0) {
            //값이 음수이면 양수로 바꿔준다.
			save *= -1;
		}
        //우선순위 큐에 삽입한다.
		q.push(save);
	}
	else {
		for (int i = before_end+1; i <= n; i++) {
            //i번 사람을 스타트팀으로 배치
			people[i] = 1;
            //이후 i+1번 사람부터 팀 배치 시작
			maketeam(curteamsiz + 1, i);
            //수행 이후 i번 사람을 다시 링크팀으로 배치
			people[i] = 0;
		}
	}
	
}

 

전체 코드

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

int arr[21][21];
int n, s;
//스타트팀은 1, 링크팀은 0
int people[21];

priority_queue <int, vector<int>, greater<int>> q;

//스타트 팀의 점수 계산 함수
int calculate_start() {
	int startscore = 0;
	vector<int> teamstart;
	for (int i = 1; i <= n; i++) {
		if (people[i] == 1) {
			teamstart.push_back(i);
		}
	}

	for (int i = 0; i < teamstart.size() - 1; i++) {
		for (int j = i + 1; j < teamstart.size(); j++) {
			startscore += arr[teamstart[i]][teamstart[j]] + arr[teamstart[j]][teamstart[i]];
		}
	}
	return startscore;
}

//링크 팀의 점수 계산함수
int calculate_link() {
	int linkscore = 0;
	vector<int> teamlink;
	for (int i = 1; i <= n; i++) {
		if (people[i] == 0) {
			teamlink.push_back(i);
		}
	}

	for (int i = 0; i < teamlink.size() - 1; i++) {
		for (int j = i + 1; j < teamlink.size(); j++) {
			linkscore += arr[teamlink[i]][teamlink[j]] + arr[teamlink[j]][teamlink[i]];
		}
	}
	return linkscore;
}


//팀을 짜는 함수
//curteamsiz : 현재 팀에 몇 명이 들어왔는가
//before_end : 몇 번 사람까지 팀에 배치를 했는가
void maketeam(int curteamsiz, int before_end) {
	//팀 인원이 모두 찰 경우(전체 인원의 절반이 스타트팀으로 배치 완료)
	if (curteamsiz == n / 2) {
		//팀 배치가 완료됐으니 스타트팀의 점수-링크 팀의 점수
		int save = calculate_start() - calculate_link();
		if (save < 0) {
			//값이 음수이면 양수로 바꿔준다.
			save *= -1;
		}
		//우선순위 큐에 삽입한다.
		q.push(save);
	}
	else {
		for (int i = before_end + 1; i <= n; i++) {
			//i번 사람을 스타트팀으로 배치
			people[i] = 1;
			//이후 i+1번 사람부터 팀 배치 시작
			maketeam(curteamsiz + 1, i);
			//수행 이후 i번 사람을 다시 링크팀으로 배치
			people[i] = 0;
		}
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> arr[i][j];
		}
	}
	maketeam(0, 1);
	cout << q.top();

}