백준 14889 _ 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

✨ 내 소스 코드

#include<iostream>
#include <vector>
#include<algorithm>
const int MAX = 2147483647;
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int stats[20][20];
	
	int N,result=MAX;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> stats[i][j];
		}
	}
    

	//비트 마스킹 방식으로 풂
    //N=4 일때, 0010 부터 1111까지의 숫자를 탐색
    //N=6 일때, 000100부터 111111까지의 숫자
	for (int i = (1 << ((N / 2) - 1)); i < (1 << N); i++) {
		
        //1의 개수를 카운트
		int bit_count=0;
        //j의 비트가 0부터 1,10,100,1000과 같이 늘어난다
        //이 값을 i와 AND연산을 하여 1인지 판별
        //ex) 0010과 01을 AND하면 0
        //ex) 0010과 10을 AND하면 10 -> 1개수 증가
		for (int j = 0; j < N;j++) {
			if (i&(1 << j)) {
				bit_count += 1;
			}
		}
        
        //1의 개수가 N의 절반인지 확인
		if (bit_count != N / 2)continue;
        
        
        //1과 0의 개수가 같을 경우, 1을 start벡터에 0을 link벡터에 넣는다
		vector<int> start, link;
		for (int j = 0; j < N;j++) {
			if (i&(1 << j)) {
				start.push_back(j);
			}
			else {
				link.push_back(j);
			}
		}
		
        //벡터에 있는 값으로 각 팀의 능력치 합산
		int start_stats = 0, link_stats = 0;
		for (int j = 0; j < N/2; j++) {
			for (int k = 0; k < N/2; k++) {
				start_stats += stats[start[j]][start[k]];
				link_stats+=stats[link[j]][link[k]];
			}
		}
		
        //최소값 구하여 결과를 도출
		int min_value = start_stats - link_stats;
		if (min_value < 0) min_value *= -1;
		result = min(result, min_value);

	}
	cout << result;


	return 0;
}

 

🙏 문제 풀이

백준의 분류를 보니 백트래팅과 비트마스킹 방식으로 풀 수 있는 것 같은데, 백트래킹보다는 비트마스킹가 효율이 좋을 것 같아 비트 마스킹 방식으로 문제를 풀어보았다

 

 

🌱 비트로 탐색

for (int i = (1 << ((N / 2) - 1)); i < (1 << N); i++) {
	
}

 

N=4일때, i는 0010 ~ 1111까지의 숫자 즉, 2 ~ 15를 탐색하게 된다

N=6일때, i는 000100 ~ 111111까지의 숫자 즉, 4 ~ 63을 탐색하게 된다

 

 

그러면 0의 개수와 1의 개수가 서로 다른 경우와 같은 경우가 섞이게 되는데

우리는 0과 1의 개수가 정확히 같은 경우만 필요하기 때문에 다음과 같은 코드를 넣어주었다

 

for (int j = 0; j < N;j++) {
	if (i&(1 << j)) {
		bit_count += 1;
	}
}

 

j는 0, 01, 10, 100, 1000과 같은 비트값으로 증가하게 된다

N=4일때, j는 0, 01, 10, 100, 1000의 값을 차례대로 가지게 되고 이 값을 i와 비트 AND 연산을 하게 된다

 

 

만약 i = 2 = 0010 이고 j=0000일 경우, i & j는 0000이 된다

j = 0001일 경우, i&j는 0000이 된다

j = 0010일 경우, i&j는 0010이 된다 따라서 1의 개수 카운트 + 1을 해준다

j = 0100일 경우, i&j는 0000이 된다

j = 1000일 경우, i&j는 0000이 된다

 

 

따라서 위의 경우에는 1과 0의 개수가 같지 않기 때문에, 다음 i의 값(0011)을 탐색해보게 된다

 

if (bit_count != N / 2) continue;

 

 

 

🌱 0과 1로 팀을 나눠 능력치 계산하기

vector<int> start, link;

for (int j = 0; j < N;j++) {
	if (i&(1 << j)) {
		start.push_back(j);
	}
	else {
		link.push_back(j);
	}
}

 

1의 개수와 0의 개수가 동일한 i 값을 찾아내면, start팀과 link팀을 분류시켜주어야한다

 

 

위에서 사용한 방식을 활용하여, 1이면 start 벡터에 값을 넣어주고

0이면 link 벡터에 값을 넣어주어서 팀을 나누게 된다

 

 

예를 들어, i = 0011이라면

j = 0000 (10진수 0), 0001 (10진수 1), 0010 (10진수 2), 0100 (10진수 3), 1000 (10진수 4)의 값을 차례로 가지며 반복문이 돌아가게 되는데 

0011 & 0001 = 0001 이므로, 1은 start로 분류된다

0011 & 0010 = 0010 이므로, 2는 start로 분류된다

0011 & 0100 = 0000 이므로, 3은 link로 분류된다

0011 & 1000 = 0000 이므로, 4는 link로 분류된다

 

 

int start_stats = 0, link_stats = 0;
for (int j = 0; j < N/2; j++) {
	for (int k = 0; k < N/2; k++) {
		start_stats += stats[start[j]][start[k]];
		link_stats+=stats[link[j]][link[k]];
	}
}

int min_value = start_stats - link_stats;
if (min_value < 0) min_value *= -1;
result = min(result, min_value);

 

분류 한 것을 바탕으로 start팀과 link팀의 능력치를 계산하고 이 두 팀의 최소값을 구하여 결과를 도출하면 된다

 

 

 

 

🌱 문제 풀이 결과