백준 1014번 문제 컨닝 풀이

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

1014번: 컨닝

문제 소개

백준 1014번 문제 컨닝에 대한 풀이 포스팅입니다. 사실 이 문제는 컨닝2 라는 문제도 있고, 컨닝2의 경우 컨닝1과 문제는 동일하나 N,M값이 다릅니다.

 

컨닝1은 N,M이 최대 10이고, 컨닝2는 N,M이 최대 80입니다.

 

일단 이 포스팅에서는 컨닝1을 풀이하기 위한 내용을 소개합니다.

 

사실 저는 이 문제에 대한 풀이 방법(카테고리 정도)를 알고 문제를 접근했습니다.

 

약간 스포일러를 하자면 다이나믹 프로그래밍으로 풀 수 있고 거기에 추가적인 기법이 하나 들어가게 됩니다.

 

다이나믹 프로그래밍 + 비트마스킹

일반적인 다이나믹 프로그래밍은 많이 들어보셨을 것이지만, 비트마스킹을 조합해서 쓰는 것은 잘 모르시는 분들도 있을 것입니다.

 

일단 문제를 분석해보면, 다이나믹 프로그래밍으로 풀만한 최적 부분구조(Optimal substructure)와 또 하나 특성이 있는데 그것이 성립하는 것 같습니다.

 

최적 부분구조라 함은, 부분문제의 최적값이 전체 문제의 최적값을 구하는데 사용이 된다는 것이고, 다른 하나의 특성은 부분문제의 풀이가 다른 나머지 문제를 풀 때 영향을 주지 않는다는 것이지요.

 

사실 영향을 주긴 하는데, 컨닝 문제 조건 상 앞에 줄에 사람을 어떻게 배치했느냐가 바로 뒷 줄에 사람을 배치하는 것에만 영향을 줍니다. 따라서 바로 앞줄에 사람을 어떻게 배치했는지를 저장을 할 필요가 있습니다.

 

그리고 앞에서 부터 사람을 채운다고 하면 앞에서 사람을 많이 채워놓아야지 뒤에서도 전체 사람 수를 채우는 데 도움이 되므로 최적 부분구조가 성립한다고 할 수 있겠지요.

 

그런데 사람을 배치하는 것은 한 줄(row)단위로 생각하면 사람이 있다, 없다의 2진수로 표현이 가능하게 됩니다.

 

컴퓨터에서는 정수를 2진수로 표현하기 때문에 이를 이용해서 앞 줄의 사람이 앉아있는 상태를 정수 하나로 쉽게 표현할 수 있을 것 같습니다.

 

이러한 방식을 bitmasking이라고 합니다.

 

점화식 정의

일단 사람을 앞에서 부터 채워야지, 이전에 앞에 채운 사람의 형태에 따라 뒤에서 valid한 사람 배치, invalid한 사람 배치를 알 수 있으므로 for-loop를 이용한 동적계획법으로 풀이를 하려고 설계를 해 보겠습니다.

 

그러면 점화식을 정의를 해 보아야 하는데 다음과 같습니다.

//(dp[i][j]//)

여기서 i는 i번째 열까지 채웠을때의 상태를 나타내고, j는 해당 i번째 열에 사람을 어떻게 배치했느냐를 나타냅니다.

즉 점화식의 정의는 i번째 열까지 사람을 다 채우고, i번째 열에는 사람을 j의 비트 모양으로 배치했을 때 가장 많이 배치할 수 있는 사람의 수라고 보시면 됩니다.

 

그러면 //(j//)모양으로 사람을 배치한다는 것은 무슨 말이 될까요?

 

간단하게 //(j=5//)라고 한다면 5는 2진수로 표현하면 101이 됩니다. 그러면 1이 있는 자리에는 사람이 있는 것이고, 0이 있는 자리에는 사람이 없는 것입니다. 이러한 방식으로 사람을 앉힌다는 것이지요.

 

구현전략

그러면 이러한 알고리즘으로 풀이 코드를 구현해보도록 하겠습니다.

 

그런데 보면 학생은 양 옆의 자리를 컨닝할 수 있으므로, 바로 인접하여 2명의 학생이 옆으로 배열되는 경우는 없습니다.

따라서 bit 들 중에서 인접한 2개의 bit가 같이 1로 되어있는 경우는 제거를 합니다. 그리고 이 bit 집합들은 자주 쓰일 것 같으므로 한번 만든 뒤 계속 사용하도록 하겠습니다.

 

그리고 비트마스킹의 장점 중 하나가, 모든 비트 경우를 확인하는 것은 단지 for-loop하나를 돌리면 다 확인이 가능합니다.

 

이러한 전략들을 적용하여 코드를 작성해보도록 하겠습니다.

 

풀이 코드

 

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
string field[15];
int dp[15][1025]; // dp[i][j]=> i번째 줄에 j비트 모양으로 학생을 배치할때, i번째까지 사람을 앉힐 수 있는 최대수
bool seat_check(string& seats, int bit) {
	for (size_t i = 0; i < seats.length(); i++) {
		if (seats[i] == 'x' && (bit & (1 << i))) return false;
	}
	return true;
}
bool adj_check(int bit, int width) {
	for (int i = 0; i < width - 1; i++) {
		int val = (3 << i);
		if ((bit & val) == val) return false;
	}
	return true;
}
bool bits_check(int bit, int fbit, int width) {
	//앞자리랑 뒷자리 관계가 제대로 성립하는지 확인
	for (int i = 0; i < width; i++) {
		if ((1 << i) & fbit) { //앞자리에 앉는 녀석이 있을 때
			if (i > 0 && ((1 << (i - 1)) & bit)) return false; //왼쪽에 뒤에 앉는 경우
			if ((1 << (i + 1) & bit)) return false; //오른쪽 뒤에 앉는 경우
		}
	}
	return true;
}
void solve() {
	int ans = 0;
	memset(dp, 0, sizeof(dp));
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> field[i];
	}
	vector<pii> bits_set; //인접한 자리가 아닌 비트 마스크들을 미리 만들어놓음.
	for (int bit = 0; bit < (1 << m); bit++) {
		if (adj_check(bit, m)) {
			int cnt = 0;
			for (int i = 0; i < m; i++) {
				if ((1 << i) & bit) cnt++;
			}
			bits_set.push_back(make_pair(bit, cnt));
		}
	}
	for (int i = 1; i <= n; i++) {
		//i 번째 줄을 채울 예정
		for (pii bit : bits_set) {
			if (!seat_check(field[i], bit.first)) continue; //부서진 자리에 앉으려고 하는 경우
			for (pii fbit : bits_set) { //앞자리 앉는 녀석
				if (bits_check(bit.first, fbit.first, m)) {
					dp[i][bit.first] = max(dp[i][bit.first], dp[i - 1][fbit.first] + bit.second);
					ans = max(ans, dp[i][bit.first]);
				}
			}
		}
	}
	cout << ans << endl;
	return;
}
int main() {
	int tc; cin >> tc;
	while (tc--) solve();
}