[14391번 종이 조각] - C++

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

완전탐색 혹은 비트마스킹으로 풀 수 있는 문제다. 필자는 풀지 못했다. 완탐도 비트마스킹도 어떻게 푸는지 방법을 알아내지 못해 다른 블로그(https://regularmember.tistory.com/90)의 풀이를 참고했다. 비트마스킹으로 풀고 싶어 비트마스킹 풀이를 참고했다.

풀이

비트마스킹을 사용하기 위해 0,1에 해당하는 상태를 먼저 정의해야 한다. 여기서 0은 가로로 자르는 경우, 1은 세로로 자르는 경우로 정의한다.

123
321

위의 예시처럼 입력이 주어질 때, 초반 세팅을 위 아래 행을 한 줄로 이러 붙인 모양인 000000 (123321)으로 생각한다. 즉, 두 행 모두를 가로로 자르는 경우부터 시작한다. 종료 조건은 111111이 될 때 종료한다. 즉, 세 열 모두를 세로로 자르는 경우에 종료한다. 총 얻게 되는 2^(N*M)의 경우(000001, 000010, 000011, ...)에 맞춰 가로로 자르는 점수를 구하고, 세로로 자르는 점수를 구해 두 가지 점수를 더해준다. 더해준 점수의 최댓값을 구하면 된다.

가로로 자르는 경우, 한 행의 최대 길이에 도달하게 되면 그때까지 더했던 값 tmp를 sum 변수에 더하고 0으로 초기화한다. 중간에 1을 만나게 되면 그 때도 sum 변수에 더하고 tmp 를 0으로 초기화한다.

세로로 자르는 경우도 비슷하다. 방향만 세로로 바꿔 한 열의 최대 길이에 도달하게 되면 그때까지 더했던 값을 sum 에 더하고 tmp 값을 0으로 초기화한다. 중간에 1을 만나게 되면 그 때도 sum 변수에 더하고 tmp 를 0으로 초기화한다.

이렇게 구해진 sum 을 ans 와 비교하여 ans 보다 값이 커질 때마다 ans 의 값을 sum 으로 갱신한다.

C++ 코드

#include <bits/stdc++.h>

#define ll long long
using namespace std;
typedef pair<int,int> pint;
typedef vector<int> vint;
const int INF = 0x3f3f3f3f; const int mINF = 0xc0c0c0c0;
const ll LINF = 0x3f3f3f3f3f3f3f3f; const ll mLINF = 0xc0c0c0c0c0c0c0c0;

int ans;
int N,M;
int bd[4][4];

void sol() {
	for(int b=0;b<(1<<(N*M));++b) {
		int sum = 0;
		for(int i=0;i<N;++i) {
			int tmp = 0;

			for(int j=0;j<M;++j) {
				int k = i*M+j;

				if((b & (1<<k)) == 0) {
					tmp = tmp*10 + bd[i][j];
				} else {
					sum += tmp;
					tmp = 0;
				}
			}

			sum += tmp;
		}

		for(int j=0;j<M;++j) {
			int tmp = 0;

			for(int i=0;i<N;++i) {
				int k = i*M+j;

				if((b & (1<<k)) > 0) {
					tmp = tmp*10 + bd[i][j];
				} else {
					sum += tmp;
					tmp = 0;
				}
			}
			sum += tmp;
		}

		ans = max(ans,sum);
	}

	return;
}

int main() {
	// ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	scanf("%d %d", &N, &M);
	for(int i=0;i<N;++i) {
		for(int j=0;j<M;++j) {
			scanf("%1d", &bd[i][j]);
		}
	}
	
	sol();
	
	printf("%d\n", ans);

	return 0;
}

실행결과