브루트포스_연습2

1. 스타트와 링크 -> 비트마스크 활용하기

핵심은 스타트와 링크, 총 2팀!!
2팀이기에 0과 1 이진수를 통해 bitmask로 해결

0 ~ (1<<n) 일 때까지 0과 1을 체크하면서 체크
bit가 1이면 A팀, 0이면 B팀

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

14889번: 스타트와 링크

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

int main() {
	int n;
	cin >> n;
	vector<vector<int>> d;

	// 입력
	for (int i = 0; i < n; i++) {
		vector<int> temp(n);
		for (int j = 0; j < n; j++)
			cin >> temp[j];
		d.push_back(temp);
	}

	// bitmask 활용
	int min = 2000;

	// 1 ~ 2^n-1
	for (int i = 0; i < (1 << n); i++) {
		// 개수 확인(팀 반반 갈리는지)
		int cnt = 0;

		for (int j = 1; j < (1 << n); j=j<<1) {
			if (i & j)
				cnt++;
		}

		if (cnt == n / 2) {
			// 각각팀 확인
			int first = 0, second = 0, check = 0;
			vector<int> f, s;
			for (int j = 1; j < (1 << n); j = j << 1) {
				if (i & j)
					f.push_back(check);
				else
					s.push_back(check);
				check++;
			}

			// 계산
			for (int j = 0; j < f.size(); j++) {
				for (int k = 0; k < f.size(); k++) {
					first += d[f[j]][f[k]];
					second += d[s[j]][s[k]];
				}
			}

			// 비교
			int val = abs(first - second);
			if (min > val)
				min = val;
		}
	}
	// 출력
	cout << min;
}

2. 종이 조각

3자리 < 4자리가 무조건 크다는 사실을 생각해보면
무조건 4자리여야 하는게 아닐까?
반례 존재, 0을 활용할 경우 

4자리로 자르는 경우 최대값은 5005

다음과 같이 자르면 최대값 5500

그래서 모든 방식을 사용해야 한다.
모든 칸은 가로 칸, 세로 칸에 속한다는 사실을 활용
두 가지 경우 -> 비트마스크 (가로 0, 세로 1 로 두고 구해보기!)

2^(NM) 의 경우의 수 
2^16 = 65536
가로 계산 , 세로 계산 따로 진행

문제 : https://www.acmicpc.net/problem/14391

14391번: 종이 조각

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

int main() {
	int n, m, maxVal = -1;
	cin >> n >> m;

	// 입력
	vector<vector<int>> d;
	for (int i = 0; i < n; i++) {
		vector<int> temp(m);
		for (int j = 0; j < m; j++) {
			char ch;
			cin >> ch;
			temp[j] = ch - '0';
		}
		d.push_back(temp);
	}

	// 0~ 1^(n+m)-1
	for (int i = 0; i < (1 << (n*m)); i++) {
		int sum = 0;
		
		// 행 체크(가로 0) 가로우선 탐색
		for (int j = 0; j < n; j++) {
			int temp_sum = 0;
			for (int k = 0; k < m; k++) {
				int bit = 1 << ((j*m) + k);
				// 가로
				if (!(i & bit))
					temp_sum = temp_sum * 10 + d[j][k];
				// 세로
				else {
					sum += temp_sum;
					temp_sum = 0;
				}
			}
			sum += temp_sum;
		}
		
		// 열 체크(세로 1) 세로우선 탐색
		for (int j = 0; j < m; j++) {
			int temp_sum = 0;
			for (int k = 0; k < n; k++) {
				int bit = 1 << ((k*m) + j);
				// 세로
				if (i & bit)
					temp_sum = temp_sum * 10 + d[k][j];
				// 가로
				else {
					sum += temp_sum;
					temp_sum = 0;
				}
			}
			sum += temp_sum;
		}
		
		// 비교
		if (maxVal < sum)
			maxVal = sum;
	}
	cout << maxVal;
}