백준 14391번 종이 조각

문제 링크입니다: https://www.acmicpc.net/problem/14391

14391번: 종이 조각

 

이 문제의 핵심은 정사각형 칸을 어떻게 쪼갤 것인지를 구현하는 과정에 있었습니다.

아래와 같이 비트마스킹을 이용하여 모든 경우의 수를 탐색하면 풀 수 있습니다.

• 0: 숫자를 가로로 이어 붙인다
• 1: 숫자를 세로로 이어 붙인다

 

 

위 표를 비트마스킹으로 구현하면 아래와 같습니다.

• 0001110111110011

 

위 비트를 주어진 N, M을 기반으로 표로 만들면 다음과 같습니다. 

 

 

	#include <iostream>
	#include <algorithm>
	#include <string>
	#include <vector>
	using namespace std;
	const int MAX = 4;
	int N, M;
	int result;
	int board[MAX][MAX];
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int y = 0; y < N; y++)
	{
	string s;
	cin >> s;
	for (int x = 0; x < M; x++)
	{
	board[y][x] = (s[x] - '0');
	}
	}
	for (int bit = 0; bit < (1 << (N * M)); bit++)
	{
	int sum = 0;
	for (int y = 0; y < N; y++)
	{
	int temp = 0;
	for (int x = 0; x < M; x++)
	{
	int k = y * M + x;
	if (!(bit & (1 << k)))
	{
	temp *= 10;
	temp += board[y][x];
	}
	else
	{
	sum += temp;
	temp = 0;
	}
	}
	sum += temp;
	}
	for (int x = 0; x < M; x++)
	{
	int temp = 0;
	for (int y = 0; y < N; y++)
	{
	int k = y * M + x;
	if (bit & (1 << k))
	{
	temp *= 10;
	temp += board[y][x];
	}
	else
	{
	sum += temp;
	temp = 0;
	}
	}
	sum += temp;
	}
	result = max(result, sum);
	}
	cout << result << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

 

참고

인프런 10주완성-코딩테스트 - 큰돌 강사님