[PS] 컨닝 / C++ (백준 1014번)

컨닝 (백준 1014번)

 

dfs로 풀면 시간 초과 이므로, 다른 풀이를 떠올려야 하는데 그 부분이 너무 막막했던 문제.

 

풀이과정

 비트필드를 이용한 dp로 풀면 된다.

1. m(가로) 길이에 맞게 자리에 앉을 수 있는 모든 경우의 수를 비트 마스크로 생성한다.
   • {0, 1}, {0, 1, 10}, {0, 1, 10, 100, 101}, {0, 1, 10, 100, 101, 1000, 1001, 1010}과 같이 피포나치 수열로 증가세를 띄며, 가로 길이가 최대인 10일 경우 144가지 경우의 수가 있다.
   • 이를 b_mask에 저장하고 점화식을 'dp[i][j]=i번째 줄에서 b_mask[j]의 비트 값으로 앉을 때, 최대로 앉을 수 있는 인원'으로 세운다.
2. 첫 줄의 dp 값은 b_mask의 1의 개수로 저장한다.
3. 두 번째 줄부터 각 줄 마다 다음 작업을 진행한다.
   • 모든 mask들에 대해 현재 줄이 mask의 비트 값으로 앉을 수 있는지 학생 배치(input)를 확인한다.
   • 앉을 수 있다면 mask를 토대로 이전 줄에서 나올 수 없는 bomb 마스크를 만든다. (ex. mask가 1010001001이라면 bomb 마스크는 0101010110이 됨)
   • bomb 마스크를 토대로 모든 mask들에 AND 연산을 하여 이전 줄에 앉을 수 있는 mask(AND 연산의 결과가 0인 mask)를 찾아 dp 값을 갱신한다.
     • dp[i][j]=max(dp[i][j], dp[i-1][l]+sit); sit은 현재 mask의 1의 갯수 즉, 현재 줄에 앉을 학생 수로 전처리해서 사용해도 된다.
4. dp[n-1][1~m-1] 중 최댓값을 출력한다.

 

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;

vector<int> _prev, b_mask;
char d[11][11];
int dp[11][501];

int logic()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		scanf("%s", d[i]);
	}
	
	_prev.push_back(0);
	b_mask.push_back(0);
	b_mask.push_back(1);

	for (int i = 1; i < m; i++) {
		int b_size = b_mask.size(), p_size = _prev.size();
		for (int j = 0; j < p_size; j++)
			b_mask.push_back(_prev[j] | (1 << i));
		for (int j = p_size; j < b_size; j++)
			_prev.push_back(b_mask[j]);
	}
	
	int b_size = b_mask.size();
	for (int i = 0; i < b_size; i++) {
		int sit = 0;
		for (int j = 0; j < m; j++) {
			int c = m - j - 1;
			if (b_mask[i] & (1 << j) && d[0][c] != 'x')sit++;
		}
		dp[0][i] = sit;
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < b_size; j++) {
			int f = 0;
			for (int l = 0; l < m; l++) {
				if (d[i][l] == 'x') {
					int c = m - l - 1;
					if (b_mask[j] & (1 << c)) {
						f = 1;
						break;
					}
				}
			}
			if (f == 1)continue;

			int bomb = 0, sit = 0;
			for (int l = 0; l < m; l++) {
				if (b_mask[j] & (1 << l)) {
					if (l != 0)bomb = bomb | (1 << (l - 1));
					if (l != m - 1)bomb = bomb | (1 << (l + 1));
				}
				
				if (b_mask[j] & (1 << l))sit++;
			}

			for (int l = 0; l < b_size; l++) {
				if ((bomb & b_mask[l]) == 0) {
					if (dp[i][j] == 0)dp[i][j] = dp[i - 1][l] + sit;
					else if (dp[i][j] < dp[i - 1][l] + sit)dp[i][j] = dp[i - 1][l] + sit;
				}
			}
		}
	}
	
	int dap = 0;
	for (int j = 0; j < b_size; j++) {
		if (dp[n - 1][j] > dap)dap = dp[n - 1][j];
	}
	printf("%d\n", dap);

	return 0;
}

int main()
{
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		logic();
		_prev.clear();
		b_mask.clear();
		memset(d, 0, sizeof(d));
		memset(dp, 0, sizeof(dp));
	}
	return 0;
}