백준14889 - 스타트와 링크

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

14889번: 스타트와 링크

조합을 이용하여 푼 문제이다. N개의 숫자가 주어지고 서로 다른 숫자와의 궁합이 주어진다.

 

문제를 풀기 위하여 N개 중 N/2개를 선택하였다. 선택한 것은 방문 처리를 하여 선택하지 않은 수를 일부러 뽑지 않고 구할 수 있개 하였다. N/2개를 각각 뽑은 수를 모두 더하여 차를 구한다. 제일 작은 차를 구하여 답으로 출력하면 된다.

 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#define MAX 21
using namespace std;

int small = 987654321;
int mat[MAX][MAX];
int N;
bool visit[MAX] = { false, };

vector<int> v;
vector<int> another_v;

void func(int x, int cnt) {
	if (cnt == N / 2) { //N / 2개를 뽑았다면
		another_v.clear(); //뽑지 않은 수를 뽑기 위한 벡터를 비운다.
		int sum1 = 0, sum2 = 0; //뽑은 수를 더한 합 sum1, 뽑지 않은 수를 더한 합 sum2

		//뽑지 않은 수를 구한다. 뽑지 않은 수는 방문 처리가 되어 있지 않다.
		for (int i = 1; i <= N; i++) {
			if (!visit[i]) {
				another_v.push_back(i);
			}
		}

		//뽑은 수의 합을 구한다.
		for (int i = 0; i < v.size(); i++) {
			for (int j = 0; j < v.size(); j++) {
				if (i == j) { //자기 자신은 건너뛴다.
					continue;
				}
				sum1 = sum1 + mat[v[i]][v[j]]; //서로 다른 원소끼리의 궁합을 구한다.
			}
		}
		//뽑지 않은 수의 합을 구한다.
		for (int i = 0; i < another_v.size(); i++) {
			for (int j = 0; j < another_v.size(); j++) {
				if (i == j) { //자기 자신은 건너뛴다.
					continue;
				}
				sum2 = sum2 + mat[another_v[i]][another_v[j]]; //서로 다른 원소끼리의 궁합을 구한다.
			}
		}

		small = min(small, abs(sum1 - sum2)); //가장 작은 차를 구한다.
		return;
	}
	else {
		//N개의 원소를 N / 2개로 뽑는 과정, 콤비네이션 이용
		for (int i = x; i <= N; i++) { 
			if (visit[i]) { //이미 방문한 원소이면
				continue; //무시
			}
			v.push_back(i); //뽑은 원소를 저장하고
			visit[i] = true; //뽑은 원소를 방문 처리하고
			func(i + 1, cnt + 1); //다음 인덱스로 넘어가서 탐색
			v.pop_back(); //마지막에 뽑은 원소를 삭제
			visit[i] = false; //마지막에 뽑은 원소를 미방문처리
		}
	}
}

int main() {
	//N X N 크기의 좌표 정보를 입력
	cin >> N;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> mat[i][j];
		}
	}

	func(1, 0); //1부터 조합시작

	cout << small;
}