백준 14889 스타트와 링크 (비트마스크)

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

코드가 긴건 위에 추가로 주석이 많기 때문..

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> start;
vector <int> link;

int arr[21][21];
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
		}
	}
	//입력
	int maxx = 9999999;
	//0010
	for (int i = n / 2; i <= (1 << n) - 1; i++) //4일때 짝수니까 i=2부터 15까지
	{
		int bit = 0;//비트마스크 세팅완료


		link.clear();
		start.clear();//초기화

		int cnt = 0;
		for (int j = 0; j < n; j++) //쉬프트 연산자 각각  0001 0010 0100 1000 을 담당할 예정
		{


			if (i &(1 << j))
			{//겹칠때
				start.push_back(j);
			} //i=2 ,3 ,4 ,5 ~ 15까지 가는데  2일때는 0010 5일때는 0110인데 그 위치에 j [0001 0010 0100 1000] 이 맞아떨어지면 cnt++ 
			else
			{
				link.push_back(j);
			}
		}
		int st = 0;
		int li = 0; //템프저장소
		if (start.size() == n / 2 && link.size()==n/2) // n/2번 겹친다는 뜻  즉 i는 1이 n/2개 -->예시로 4일때는 0011 0101 1001 0110 1010 1100 으로 6가지의 경우의수 각각 3, 5, 9, 6, 10, 12 인경우
		{
			
			for (int q = 0; q < n / 2; q++)  //4일때    2보다 작을때까지    2부터 p까지   0 1  10?
			{
				for (int p=0;p<n/2;p++)
				{
					if (p == q)continue;
					st += arr[start[q]][start[p]];
					li += arr[link[q]][link[p ]];
				}
			
			}
			if (abs(st - li) < maxx)
				maxx = abs(st - li);
		}
		
	


	}
	cout << maxx;


}

 

진짜 너무 어려웠다 비트마스크로 무리하게 푸려던것도 있지만 코테에도 나오는 비트마스크이다보니 열심히 공부하였다

이때 i가 뜻하는것은 n이4라고 가정하였을때 가능한 조합수는

0010~1111 까지로 세팅을 하였다 (본래 0000부터 해도 되지만 문제내 n의 수는 짝수라고 하였기에 n/2부터 시작을 하였다 [따라서 4일땐 2-->0010 6일땐 3-->000011 8일땐 4-->0000100 나름 경우의수가 줄어든다]

 

j는 이때 1이 있는 경우를 뜻하는데 마찬가지로 n=4일때는

1)0001

2)0010

3)0100

4)1000

가 되며 1이 겹치는게 n/2이면 반으로 잘 나누어진 것을 뜻한다

이때 start벡터 배열에 일단 j를 넣고(index) 추후 start.size()==link.size() 인경우

i!=j인 경우 원래 저장해두었던 arr배열에서 값을 더하여 abs를 통해 max값을 변경해 나갔다

[까다로운게 arr[i][j]와 arr[j][i]가 다를수도 있다는 점이다 짝사랑도 아니고 나원참..