[BOJ]14391번: 종이 조각 (c++)

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

14391번: 종이 조각

 

방법 1: 비트마스크

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	// 입력
	int N, M;
	cin >> N >> M;
	vector<vector<int>> P(N, vector<int>(M));
	for (int i = 0; i < N; ++i)
	{
		string tmp;
		cin >> tmp;
		for (int j = 0; j < M; ++j)
		{
			P[i][j] = tmp[j] - '0';
		}
	}

	/*
		0 : 가로방향
		1 : 세로방향

		비트마스크로 가로세로 조합
	*/
	int max_sum = 0;
	for (int bitset = 0; bitset < (1 << N * M); ++bitset)
	{
		int sum = 0;

		// 가로 숫자 합 구하기
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < M; ++j)
			{
				if (~bitset & (1 << (i * M + j)))
				{
					int num = 0;
					while (j < M && ~bitset & (1 << (i * M + j)))
					{
						num *= 10;
						num += P[i][j];
						++j;
					}
					sum += num;
				}
			}
		}

		// 세로 숫자 합 구하기
		for (int j = 0; j < M; ++j)
		{
			for (int i = 0; i < N; ++i)
			{
				if (bitset & (1 << (i * M + j)))
				{
					int num = 0;
					while (i < N && bitset & (1 << (i * M + j)))
					{
						num *= 10;
						num += P[i][j];
						++i;
					}
					sum += num;
				}
			}
		}

		// 최대합 구하기
		max_sum = max(max_sum, sum);
	}

	cout << max_sum;

	return 0;
}

 

방법 2: dfs  나중에 다시 풀기

 

boj 정답 상위권 분들은 dfs로 많이들 푸신것 같다.

나는 비트마스크 연습중이라서 비트마스크로 풀었다.

 

 

TIP_비트마스크

종이를 (가로, 세로) 2가지로 자를 수 있기 때문에 

비트마스크로 풀 수 있다. 

 

P[i][j]가 가로인지 세로인지 판단하는 부분만 조심해주면 된다.

오프셋 개념을 생각하면 편하다. 

N * M배열에서 P[i][j]는 P[0][0]에서부터 i * M + j 만큼 떨어져있다.

 

비트마스크를 검사할 때도 동일하다. 

// P[i][j]번째 숫자의 가로/세로 판단

if (bitset & (1 << (i * M + j)))
...