백준 14391 종이조각 풀이(c++)

문제

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

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

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

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

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

입력

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

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

출력

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

 

#include <iostream>
#include <vector>
#include <climits>
#include <string>
#include <algorithm>

using namespace std; 

int N, M, iResult = 0;
int rect[5][5];
bool axis[5][5] = { false };
bool visited[5][5] = { false };


int FindMax()
{
	int iSum = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (visited[i][j])
				continue;

			vector<int> vNum;
			visited[i][j] = true;
			vNum.push_back(rect[i][j]);
			int iNext = 1;
			if (axis[i][j] == true)
			{
				while (1)
				{
					if (j + iNext  >= M)
						break;
					if (axis[i][j + iNext] == true)
					{
						visited[i][j + iNext] = true;
						vNum.push_back(rect[i][j + iNext]);
						iNext++;
					}
					else
						break;
				}
			}
			else
			{
				while (1)
				{
					if (i + iNext >= N)
						break;
					if (axis[i + iNext][j] == false)
					{
						visited[i + iNext][j] = true;
						vNum.push_back(rect[i + iNext][j]);
						iNext++;
					}
					else
						break;
				}
			}
			string str = "";
			for (auto v : vNum)
				str += to_string(v);
			iSum += stoi(str);
		}
	}
	return iSum;
}

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

	cin >> N >> M;

	for (int i = 0; i < N; ++i)
	{
		string strInput;
		cin >> strInput;
		for (int j = 0; j < M; ++j)
		{
			rect[i][j]= strInput[j] - '0';
		}
	}
		


	for (int bitmask = 0; bitmask < (1 << (N * M)); ++bitmask)
	{
		for (int x = 0; x < N; ++x)
		{
			for (int y = 0; y < M; ++y)
			{
				axis[x][y] = (bitmask & (1 << (x * M + y))); 
			}
		}
		fill(&visited[0][0], &visited[0][0] + 5 * 5, false);
		iResult = max(iResult, FindMax());
	}

	cout << iResult;

	return 0;
}

 

비트마스킹과 완전 탐색을 통하여 풀이

더 효율적으로 푸는 방법을 찾아야 겠다.