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

 

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

14889번: 스타트와 링크

[문제 풀이]

완전탐색을 이용하여 문제를 풀었습니다.

 

스타트 팀과 링크 팀이 가질 수 있는 맴버의 경우 수를 모두 고려하여 check 배열에 메모제이션을 해줍니다.

 

그 후 반복문을 통해 스타트 팀과 링크 팀의 점수를 비교하여 가장 작은 수를 찾아 주었습니다.

[코드]

#include<iostream>

using namespace std;

int map[21][21];
int check[21] = { 0, };
int N;
int result = 987654321;

void bruteForce(int, int);
void score();

int main() {

	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			scanf("%d", &map[i][j]);

	for (int i = 0; i < N; i++) {
		check[i] = 1;
		bruteForce(i, 0);
		check[i] = 0;
	}

	printf("%d\n", result);

}

void score() {

	int start = 0, link = 0;

	for (int i = 0; i < N; i++) {

		if (check[i] == 1) {
			for (int j = i + 1; j < N; j++) {

				if (check[j] == 1) {
					start += map[i][j] + map[j][i];
				}

			}
		}
		else {
			for (int j = i + 1; j < N; j++) {

				if (check[j] == 0) {
					link += map[i][j] + map[j][i];
				}

			}
		}
	}

	int temp = (start > link) ? start - link : link - start;

	if (result > temp)
		result = temp;
}

void bruteForce(int idx, int cnt) {

	if (cnt == N / 2 - 1) {
		score();
		return;
	}
	
	for (int i = idx + 1; i < N; i++) {
		check[i] = 1;
		bruteForce(i, cnt + 1);
		check[i] = 0;
	}

}