[백준] 14391 종이조각

✔️ 문제 링크

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

14391번: 종이 조각

---

✔️ 문제 이해

1. 열 또는 행으로 조각을 나눴을 때, 각 조각에 써있는 숫자들의 최대 합을 구하는 문제이다. 

2. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

 

---

✔️ 설계

1. 각 칸은 가로 조각이거나, 세로 조각이다. 종이의 크기가 최대 4x4이므로 총 2^16가지 경우의 수가 나온다. 

2. 가로 조각인 경우 0, 세로 조각인 경우 1로 표시한다.

3. 2를 비트마스크로 손쉽게 구하면 된다. 

4. 예를들어 4x4에서 아래와 같은 경우를 생각해보자.

 

1101

1111

0101

0011

 

위는 1101 1111 0101 0011 와 같이 표현할 수 있다. 즉, 16 비트로 표현할 수 있다. 비트 마스크로 모든 조합을 구하는 것은 굉장히 간단하다. 1씩 더해주는 것만으로 모든 1과 0의 조합을 구할 수 있다. (직접 비트를 출력해보며 확인할 수 있다.)

5. 따라서 정수 변수 하나를 만들고 계속 +1을 해주면서 1과 0의 모든 조합을 찾고, 조합을 구할 때마다 숫자를 계산해주면 된다. 

6. 비트를 행렬로 매핑할때는 열 길이 기준으로 하면 된다. (예를들어, 4x4 행렬에서 처음 4개의 비트는 1행, 다음 4개의 비트는 2행..)

---

✔️ 문제 회고

1. 모든 경우의 수를 찾는 완전탐색 문제라고 파악했다. 행, 열별로 조합을 만들어서 풀려고 했더니, 구현이 상당히 복잡해졌다. 각 행, 열별로 조합을 찾는 것이 상당히 까다로왔다.

2. 블로그를 통해 해결 방법을 찾았는데, 비트 마스크로하면 N개에서 0~N개를 뽑는 모든 조합을 for문 하나로 굉장히 손쉽게 구현할 수 있다는 것을 배웠다. 

3. 비트 마스크는 매우 간편한 방법이다. 하지만 비트 연산에 대한 개념이 필요하다.

4. 나중에 다시 한 번 풀어봐야겠다.

---

👨🏻‍💻 소스 코드

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

int n, m;
int map[4][4];

int main() {
	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf_s("%1d", &map[i][j]);
		}
	}

	int res = -1;

	for (int bit = 0; bit < (1 << (n*m)); bit++) {
		//cout << bitset<32>(bit) << endl;
		int sum = 0;

		for (int i = 0; i < n; i++) { //가로 조각 계산
			int num = 0;
			for (int j = 0; j < m; j++) {
				int k = i * m + j;

				if ((bit & (1 << k)) == 0) {
					num = num * 10 + map[i][j];
				}
				else {
					sum += num;
					num = 0;
				}
			}
			sum += num;
		}

		for (int j = 0; j < m; j++) {//세로 조각 계산
			int num = 0;
			for (int i = 0; i < n; i++) {
				int k = i * m + j;
				if ((bit & (1 << k)) != 0) {
					num = num * 10 + map[i][j];
				}
				else {
					sum += num;
					num = 0;
				}
			}
			sum += num;
		}
		res = max(res, sum);
	}

	cout << res << endl;
	return 0;
}