[백준/C++] 종이조각

종이조각

문제 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력 첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

출력 영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력 1

2 3
123
312

예제 출력 1

435

예제 입력 2

2 2
99
11

예제 출력 2

182

풀이

예전에 풀었던 사탕게임 문제와 비슷하지만 비트마스크를 어떻게 이용해야 할지가 막막했다. 스터디원 중 한 명이 설명한 바로는, 예제에 나왔던 9의 경우 주위 상하좌우의 숫자가 칸막이를 상하, 또는 좌우로 치게 되면 어차피 0을 넣거나 1을 넣을 경우 방법의 수가 하나로 좁혀지기 때문에 가로를 0, 세로를 1로 하고 풀어도 관계가 없다고 한다. 어차피 0이나 1을 넣어도 똑같은 경우가 나오니까 최댓값만 구하는 이 문제에서는 상관없다는 것 같다.

아, 그러니까 비트마스크는 종이조각을 0과 1로 표시하는 식으로 구성한다. 0은 가로로 이어지는 조각, 1은 세로로 이어지는 조각으로 한다. 그러면 모든 종이조각 판의 경우의 수를 만들어놓고 가로로 한 번, 세로로 한 번 싹다 돌면서 합을 구하고 최댓값을 업데이트하는 식이다.

#include <iostream>
using namespace std;

int N, M;
int paper[4][4];

int countMax()
{
	int MAX = 0;
	int sum = 0;
	for(int bitMask = 0; bitMask < (1 << N * M); ++bitMask) {
		//horizonal traverse
		for(int i = 0; i < N; ++i) {
			int tmp = 1;
			for(int j = M - 1; j >= 0; --j) {
				if(~bitMask & (1 << (i * M + j))) {
					sum += tmp * paper[i][j];
					tmp *= 10;
				}
				else tmp = 1;
			}
		}
	
		//vertical traverse
		for(int i = 0; i < M; ++i) {
			int tmp = 1;
			for(int j = N - 1; j >= 0; --j) {
				if(bitMask & (1 << (j * M + i))) {
					sum += tmp * paper[j][i];
					tmp *= 10;
				}
				else tmp = 1;
			}
		}
		if(MAX < sum) MAX = sum;
		sum = 0;
	}
	return MAX;
}

int main()
{
	string temp;
	cin >> N >> M;
	for(int i = 0; i < N; ++i) {
		cin >> temp;
		for(int j = 0; j < M; ++j) 
			paper[i][j] = static_cast<int>(temp[j] - '0');
	}
	cout << countMax();

	return 0;
}