백준 14391: 종이 조각

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

 

이 문제는 몇 번 마주했지만, 도저히 답을 떠올릴 수가 없어서, 계속 넘어갔었다.

N과 M이 4 이하의 자연수라서 Bruteforce를 사용하는 것은 명백한데, 어떻게 해야할지 감이 잡히지 않았다.

문득, 알고리즘 태그에 눈이 갔는데, 비트마스크 사용을 장려해서 비트마스크를 어떻게 사용하면 될까?

에서부터 고민을 시작했다.

 

그러자, 하나 아이디어가 떠올랐다. 종이를 자르는 방법은 가로로 자르거나 세로로 자르거나 둘 중 하나이다. 그렇다면, 각 종이를 자르는 방식을 비트마스크로 나타낼 수가 있다. 이 방법의 문제는 가로로 연속으로 자르거나, 세로로 연속으로 자르는 방식은 나타낼 수 없는다는 점인데, 이 문제의 답은 합의 최대이기 때문에 연속으로 자르는 방식은 답이 아니라서, 사용할 수 있다. 그렇게 나온 코드는 다음과 같다.

 

bool 배열 대신 비트마스크를 사용하면, for문을 활용해서 쉽게 구현할 수 있다.

using namespace std;

char ch;
int N, M, G[5][5], ans = 0, P[5];

void solve2()
{
	int ret = 0;
	for (int i = 0; i < N; i++)
	{
		int s = 0;
		for (int j = 0; j < M; j++)
		{
			if (P[i] & (1 << j))
			{
				s *= 10;
				s += G[i][j];
			}
			else
			{
				ret += s;
				s = 0;
			}
		}
		ret += s;
	}
	for(int j = 0 ; j < M; j++)
	{
		int s = 0;
		for (int i = 0; i < N; i++)
		{
			if (!(P[i] & (1 << j)))
			{
				s *= 10;
				s += G[i][j];
			}
			else
			{
				ret += s;
				s = 0;
			}
		}
		ret += s;
	}
	ans = max(ret, ans);
}
void solve(int idx)
{
	if (idx == N)
	{
		solve2();
		return;
	}
	for (int n = 0; n < (1 << M); n++)
	{
		P[idx] = n;
		solve(idx + 1);
		P[idx] = 0;
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for(int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			cin >> ch;
			G[i][j] = (ch - '0');
		}
	solve(0);
	cout << ans << '\n';
}

백트래킹을 활용해서, 비트마스크 값을 정하고, 비트를 순회하며, 합을 구했다.

사실 이 문제의 답은 예전에 떠올렸지만, 구현이 귀찮아서, 문제 해결을 미뤘었다.

그런데, 다른 문제들을 최대한 구글링없이 해결하려다 보니까, 오늘의 문제 해결이 늦어져서, 지금 풀게 되었다.

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

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

뭔가 답이 떠오를 듯 말 듯해서, 답답하다..