[백준] 14889 스타트와 링크

[백준] 14889 스타트와 링크

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

• 비트마스크 이용하여 브루트 포스

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

typedef long long ll;

ll bitCount(ll x) {
	if (x == 0) return 0;
	return (x % 2) + bitCount(x / 2);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin >> n;

	//0으로 초기화한 n*n 벡터
	vector<vector<int>> S(n, vector<int>(n, 0));

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int s;
			cin >> s;
			S[i][j] = s;
		}
	}

	//팀의 능력치의 차이의 최솟값
	int minD = 987654321;

	//팀 조합 비트마스크로 표현
	//비트마스크에 포함된 팀 = 스타트 팀
	//비트마스크에 포함되지 않은 팀 = 링크 팀
	ll team;
	for (team = 0LL; team < (1 << n) - 1; ++team) {
		if (bitCount(team) != (n / 2)) continue;
		
		int startTeam = 0; //스타트 팀 점수
		int linkTeam = 0;  //링크 팀 점수

		for (int i = 0; i < n; ++i) {
			//i번 선수 무슨 팀인지 표시
			//flag = 1: 스타트 팀
			//flag = 0: 링크 팀
			int flag; 
			if (team & (1 << i)) flag = 1; 
			else flag = 0;

			//Sij 계산
			for (int j = 0; j < n; ++j) {
				//i번 선수 스타트 팀인 경우 j선수도 스타트 팀이어야
				if (flag) {
					if (team & (1 << j)) startTeam += S[i][j];
					else continue;
				}
				//i번 선수 링크 팀인 경우 j선수도 링크 팀이어야
				else {
					if (team & (1 << j)) continue;
					else linkTeam += S[i][j];
				}
			}
		}
		minD = min(minD, abs(startTeam - linkTeam));
	}

	cout << minD;
	return 0;
}

1년 전 풀이

• 백 트래킹 이용하여 브루트 포스

#include <iostream>
#include <memory.h>
#include <limits.h>
using namespace std;

//총 사람 수
int n;
int S[20][20] = { 0 };

//두 팀의 능력치의 차이의 최솟값
int bestmin;


//member[i]: i번 선수의 정보
//member[i] = 1: i번 선수 1번 팀에 소속됨
//member[i] = 0: i번 선수 0번 팀에 소속됨
int member[20] = { 0 };


//pickMem: 1번 팀에 들어갈 멤버를 고르는 함수
//start: start번 이상의 번호를 가진 선수 선택
//numOfMem: 지금까지 고른 팀 멤버 수
void pickMem(int start, int numOfMem) {
	//n번 이상의 번호를 사진 선수는 없으므로 선택 종료
	if (start == n) return;
	
	//n/2명 이상의 멤버를 고를 수 없으므로 선택 종료
	if (numOfMem > (n / 2)) return;

	//n/2명의 멤버를 고른 경우 
	if (numOfMem == (n / 2)) {
		//현재 고른 팀들의 능력치 차이
		int cand = getsum(0) - getsum(1);
		//능력치 차이 음수인 경우 -1 곱해줌
		if (cand < 0) cand *= (-1);

		//능력치 차이 최솟값 bestmin에 저장
		if (bestmin > cand) bestmin = cand;
		return;
	}

	//start번 선수를 멤버로 선택하지 않는 경우
	pickMem(start + 1, numOfMem);
	
	//start번 선수를 멤버로 선택하는 경우
	member[start] = 1;
	pickMem(start + 1, numOfMem + 1);
	member[start] = 0;

	return;
}

//팀에 소속된 선수들의 능력치의 합 계산
//team = 1: 1팀에 소속된 선수들의 능력치 합 계산
//team = 0: 0팀에 소속된 선수들의 능력치 합 계산 
int getsum(int team) {
	int sum = 0;
	for (int i = 0; i < n; i++) {
		if (member[i] != team) continue;

		for (int j = 0; j < n; j++) {
			if (member[j] != team) continue;

			if (i == j) continue; //S[i][j] == 0
			sum += S[i][j];
		}
	}
	return sum;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> S[i][j];

	bestmin = INT_MAX;

	pickMem(0, 0);

	cout << bestmin << endl;
	return 0;
}