백준 14391번 종이 조각 (C++)

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

14391번: 종이 조각

문제를 처음 봤을 때, N과 M이 겨우 5밖에 안되기 때문에 브루트포스를 하면 해결 할 수 있을 것이라는 확신이 들었다. 그러나 모든 가로 세로를 조합하며 종이를 자르는 것이 내 실력으로 할 수 없었다. 이것도 연습을 해야할 것 같다.

예제들은 모두 N자리 혹은 M 자리로만 해결하면 되는 예제만 줘서 마치 애드혹으로 보일 수 있는데 당연하지만 조합을 해야 풀 수 있는 문제이다.

계속 풀지 못하다가 알고리즘 분류를 확인하니 비트마스킹을 확인했다. 문제는 비트마스킹을 내가 한 번도 경험해보지 못했다는 것이다.

문제는 비트마스킹으로 배열을 표현하고 0,1 로 가로 세로를 표현하는 것이었다.

2x2 배열이라고 가정할 때

배열은 0000 네자리로 표현가능하고 이것을 2진수라고 하면 2^4 = 16가지의 조합이 가능하다.

예를들어 1100이라면 배열은

11

00

이된다. 그리고 1 → 가로, 0 → 세로 라 하고 배열을 순회하며 값을 구하면 되는 문제이다.

그러므로 시간 복잡도는 2^16이 최대이다.

하루를 고생하고 구글링을 하고도 풀기가 너무 어려웠다..

#include <iostream>

using namespace std;

int paper[5][5];
bool check[5][5];

int main() {
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);

int n, m;

cin >> n >> m;

for (int i = 0; i < n; i++) {
	string tmp;
	cin >> tmp;
	for (int j = 0; j < tmp.size(); j++) {
		paper[i][j] = tmp[j] - '0';
	}
}

int answer = 0;

for (int i = 0; i < (1 << (n * m)); i++) {
	int result = 0;
	// x = k
	// y = j
	for (int j = 0; j < n; j++) { // 가로부터 계산
		int sum = 0;
		for (int k = 0; k < m; k++) {
			if (i & (1 << (j * m + k))) { // 1번째 비트가 1이면
				result += sum;
				sum = 0;
			}
			else { // 0이면
				sum = 10 * sum + paper[j][k];
			}
		}
		result += sum;
	}

	for (int k = 0; k < m; k++) { // 세로 계산
		int sum = 0;
		for (int j = 0; j < n; j++) {
			//cout << paper[j][k];
			if (i & (1 << (j * m + k))) { // 1번째 비트가 0이면
				sum = 10 * sum + paper[j][k];
			}
			else { // 1이면
				result += sum;
				sum = 0;
			}
		}
		result += sum;
	}
	if (answer < result) answer = result;
}
cout << answer << endl;
}