[BaekJoon 14319] 종이조각

안녕하세요. 오늘은 백준 14319번 종이조각이라는 문제를 풀어보도록 하겠습니다.

 

해당 문제는 아래의 링크에서 확인하실 수 있습니다.

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

14391번: 종이 조각

 

우선 문제를 살펴보면

 

 

 

인풋의 범위가 매우 작습니다. 4x4까지이기 때문에 완전 탐색으로 충분히 풀리는 문제입니다.

 

또한 이 문제가 완전탐색에 적합한 이유는 가로 방향과 세로 방향밖에 없습니다.

 

즉 

저희가 흔히 생각하는

 

이런 모양이나 

 

이런 모양은 나오지 않습니다.

 

따라서 사전에 4x4 크기에 대해 0과 1 값으로 모든 경우의 수를 구합니다. -> 2^16

 

만약에 1이라면 가로로 묶고, 0이라면 세로로 묶습니다.

 

이 문제에 대해 설명하기가 조금 어려워서 다른 블로그를 참고해봤는데, 

https://vixxcode.tistory.com/23

14391번 종이조각 백준 파이썬

 

이분이 그려놓은 그림이 설명이 잘 되는 것 같습니다.

 

결론을 짓자면, 2^(n*m)에 대한 모든 경우의 수를 미리 구해놓고,

 

가로로 묶을 수 있는거 모두 확인

세로로 묵을 수 있는거 모두 확인

 

한 뒤, 만약에 여러개로 묶인다면 묶일 때마다 현재 합 * 10 + 새로운 값의 형식으로 값을 경신해주시면 됩니다.

 

<소스 코드>

#include <bits/stdc++.h>

using namespace std;
int n, m, res, sum;
int board[5][5];
bool visited[5][5];
string inp;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> inp;
		for(int j = 0; j < inp.size(); j++) {
			board[i][j]=inp[j]-'0';
		}
	}
	
	for(int i = 0; i < 1<<(n*m); i++) {
		int current_case = i, check_case = 0, total_sum = 0;
		
		for(int j = 0; j < n; j++) {
			for(int k = 0; k < m; k++) {
				check_case = j*m + k;
				if(current_case&(1<<check_case)) {
					sum = sum*10 + board[j][k];
				}	
				else {
					total_sum += sum;
					sum = 0;
				}
			}
			total_sum += sum; sum = 0;
		}
		
		for(int j = 0; j < m; j++) {
			for(int k = 0; k < n; k++) {
				check_case = j+k*m;
				if((current_case&(1<<check_case)) == 0) {
					sum = sum*10 + board[k][j];
				}	
				else {
					total_sum += sum;
					sum = 0;
				}
			}
			total_sum += sum; sum = 0;
		}
		res = max(total_sum, res);
	}
	
	cout << res << endl;
	return 0;
}

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.