BOJ14391/ C++

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

14391번: 종이 조각

 

백준 온라인저지 14391번 문제입니다. 

비트마스킹을 이용해서 풀었습니다.

 

#include<iostream>
#include<string>
#define MAX 4

using namespace std;

int n, m;
int arr[MAX][MAX];

int max(int a, int b) {
	return a > b ? a : b;
}

void Input() {
	cin >> n >> m;
	string s;
	for (int i = 0; i < n; i++) {
		cin >> s;
		for (int j = 0; j < m; j++) {
			arr[i][j] = s[j] - '0';
		}
	}
}

void solution() {
	int ans = 0;
	for (int s = 0; s < (1 << (n*m)); s++) {
		int sum = 0;

		//가로
		for (int i = 0; i < n; i++) {

			int now = 0;
			for (int j = 0; j < m; j++) {

				int k = i * m + j;
				
				//가로인경우
				if ((s&(1 << k)) == 0) {
					now = now * 10 + arr[i][j];
				}
				else {
					sum += now;
					now = 0;
				}
			}
			sum += now;
		}

		//세로
		for (int j = 0; j < m; j++) {

			int now = 0;
			for (int i = 0; i < n; i++) {
				int k = i * m + j;

				//세로인경우
				if ((s&(1 << k))!=0) {
					now = now * 10 + arr[i][j];
				}

				else {
					sum += now;
					now = 0;
				}


			}
			sum += now;
		}
		ans = max(sum, ans);
	}
	cout << ans;
}

int main(void) {
	Input();
	solution();
}

아이디어

종이를 가로 세로로 자를 수 있는 모든 경우의 수를 다 확인을 해봐야하는데 그 잘려진 상태를 비트로 표현을 하여 계산을 해야함 n차 행렬을 모두 펴서 한줄의 비트로 표현을 해야함 예를들어

123                     0 0 0 0 0 0

456  같은 경우에는 1 2 3 4 5 6 과 같이 비트로 표현 할 수 있고 해당 영역이 가로로 잘렸는지 세로로 잘렸는지는 

0과 1으로 표현 할 수 있음 여기서는 0을 가로 1을 세로로 정하였음

가로 또는 세로 비트를 확인 할때 연속으로 표현된 비트가 있다면 앞의 숫자에 10을 곱하여 현재 수를 더함으로써

종이가 길게 잘렸을때의 숫자를 보장해줌 

 

브루트 포스로 풀 수 도 있으나 방법이 크게 다르지 않고 비트마스킹으로 푸는 방식이 깔끔해보여서 시도해보지 않았음