백준 1014번 컨닝

 

문제 링크 : https://www.acmicpc.net/problem/1014

 

문제

 

N행 M열 크기의 직사각형 교실이 주어지고, 각 교실은 1x1 단위 정사각형으로 이루어져 있다.

컨닝을 방지하기 위해 모든 학생은 자신의 왼쪽, 오른쪽, 왼쪽 대각선 위, 오른쪽 대각선 위에 다른 학생이 없도록 자리배치를 하고자 할 때, 교실에 배치할 수 있는 최대 학생 수를 구하여라.

 

풀이

 

문제를 보고, 가장 먼저 든 생각은 "다 해볼 수 있는 가?"였다.

물론 최대 10x10 정사각형의 교실이 주어지면, 각 교실 자리는 100개이고, 모든 경우의 수를 다 해보는 것은

2^100 이므로 당연히 불가능하다.

 

하지만, 이 문제의 경우 i번 째 줄이 어떤 상태이고, 이 상태 배치의 경우 최대 학생 수를 알 수 있다면

i+1번째 줄을 구성하는 데에는 i번 째 줄만 신경 쓰면 된다. 그 위에 줄은 어차피 컨닝할 수 없기 때문이다.

 

따라서 모든 경우의 수를 볼 필요 없이, 그 현재 열과 윗 열의 배치만 컨닝을 하지 못하게 맞추면 되고, 그렇게 맞추면 다음엔 아래 열로 내려가 똑같이 맞추면 된다.

이 경우 비트 필드를 이용하면 가로길이가 최대 10이므로 O(2^10^2)로 "다 해볼 수 있다"

 

요약하자면, 전체 문제를 부분 문제의 구성으로 풀어냈고, 비트 필드를 이용하였기 때문에 문제 유형은 비트 필드를 이용한 다이내믹 프로그래밍이다.

dp table 구성은 이러하다.

 

dp[row][state] = 현재 row행이 state 상태일 경우, 배치할 수 있는 최대 학생 수

 

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int dp[11][(1 << 10)]; //dp[row][state] : row행에 state일 때 최대 학생의 수
string arr[11];
string state[(1 << 10)];
int n, m;

string ret_bin(int x) {
	string tmp = "";
	while (x) {
		if (x % 2 == 0) tmp += '0';
		else tmp += '1';
		x /= 2;
	}
	while (tmp.size() < m) tmp += '0';
	reverse(tmp.begin(), tmp.end());
	return tmp;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	

	int t; cin >> t;
	while (t--) {
		memset(dp, 0, sizeof(dp));

		cin >> n >> m;
		for (int i = 0; i < (1 << m); i++) {
			state[i] = ret_bin(i);
		}
		for (int i = 0; i < n; i++) cin >> arr[i];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < (1 << m); j++) {
				//행 체크
				string bin_str = state[j];
				bool flag = false; int cnt = 0;
				for (int a = 0; a < bin_str.size(); a++) {
					if (bin_str[a] == '1' && arr[i][a] == 'x') {
						flag = true;
						break;
					}
					if (bin_str[a] == '1' && a < bin_str.size() - 1) {
						if (bin_str[a + 1] == '1') {
							flag = true;
							break;
						}
					}
					if (bin_str[a] == '1') cnt++;
				}
				if (flag) continue;

				if (i == 0) {
					dp[i][j] = cnt;
					continue;
				}

				//윗 행 체크
				for (int k = 0; k < (1 << m); k++) {
					string up_str = state[k]; // 윗 행
					if (dp[i - 1][k] == 0) continue; //불가능한 배열이라면 pass
					flag = false;
					for (int a = 0; a < bin_str.size(); a++) {
						if (bin_str[a] == '1') {
							if (a > 0 && up_str[a - 1] == '1') {
								flag = true;
								break;
							}
							if (a < bin_str.size() - 1 && up_str[a + 1] == '1') {
								flag = true;
								break;
							}
						}
					}
					if (flag) continue;
					dp[i][j] = max(dp[i][j], cnt + dp[i - 1][k]);
				}
			}
		}
		int ans = 0;
		for (int i = 0; i < (1 << m); i++) {
			ans = max(ans, dp[n - 1][i]);
		}
		cout << ans << "\n";
	}
	return 0;
}