백준 BOJ 15661 - 링크와 스타트

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

15661번: 링크와 스타트

비트마스킹을 사용해서 풀었다.

재귀로 풀어도 상관없다.

비트마스킹을 통해서 팀 A와 B를 구분해주었다.

i번째 비트가 1으로 켜져있다면 i번째 사람은 A팀에 들어간 것이고

i번째 비트가 0으로 꺼져있다면 i번째 사람이 B팀에 들어간 것이다.

 

사람 20명으로 만들어 낼 수 있는 모든 경우에 대해서,

O(N^2) 로 두 사람을 골라낸 다음 그 두 사람이 같은 팀에 있다면 능력치 계산을 해주면 된다.

 

A팀의 능력치 a와 B팀의 능력치 b가 있을때, 정답을 abs(a-b) 값과 비교하며 갱신해 나가면

AC를 받는다.

 

시간제한이 상당히 아슬아슬한 편이다.

내가 풀이를 느리게 구상한건지, 혹시 더 깔끔한 풀이가 있는지는 모르겠다만

일단 O(2^N * N^2) 소스코드로 정답을 받기는 했다.

 

혹시모르니 비트연산자를 사용하도록 하자.

일반 산술연산이나, 특히 제곱을 계산하기 위한 pow() 보다는 비트연산자가 빠르다.

#include <bits/stdc++.h>
using namespace std;

int S[50][50] = {0};

int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			cin >> S[i][j];
		}
	}
	
	int ans = 998244353;
	for(int K=0; K<(1<<N); K++){
		
		int A = 0;
		int B = 0;
		
		for(int i=0; i<N; i++){
			for(int j=0; j<N; j++){
				if(K & (1<<i) && K & (1<<j)){
					A += S[i][j];
				}
				
				if(!(K & (1<<i)) && !(K & (1<<j))){
					B += S[i][j];
				}
			}
		}
		
		ans = min(abs(A-B), ans);
	}
	
	cout << ans;
	return 0;
}