BOJ1014 컨닝

 

1014번 컨닝

N*M크기의 직사각형 교실에서 컨닝을 방지하도록 앉힐 수 있는 최대 학생 수를 구한다.

현재 위치를 기준으로 동일 행의 좌우(←→), 윗 행 좌우 대각선(↖↗) 위치의 답지를 베낄 수 있다.

 

 

비트마스킹 + DP

학생이 앉은 상태, 앉을 수 없는 자리 등을 bit로 표현하고

i행에서 k의 상태로 앉을 수 있는 학생 수의 최댓값을 i-1행을 고려해 구한다. 

 

 

* 3줄 요약

cnt[ k ]  행의 상태가 k일 때 해당 행에 앉는 학생의 수 (= k를 이진수로 나타낼 때 1의 개수)

dp[ i ][ k ]  i행에 k의 상태로 앉을 때의 최대 학생 수

dp[ i ][ k ] = dp[ i-1 ][ up ] + cnt[ k ] (up은 i행의 상태가 k일 때 i-1의 상태로 가능한 것 중 dp값이 가장 큰 값)

 

 

---

 

0. 초기 정보

한 행에 대해 학생이 앉아있는 자리를 bit로 표현하면

M≤10이므로 한 행의 상태를 0부터 1023까지의 수로 나타낼 수 있다.

이후 아래와 같이 cnt배열을 채운다.

cnt[ k ]  행의 상태가 k일 때 앉은 학생의 수 (0≤k≤1023)

line 2~5: 먼저 불가능한 상태(=학생이 연속으로 앉아있는 상태)를 처리한다.

line 6~9: 가능한 상태에 대해 학생 수를 구한다.

	int cnt[1024] = { 0, };
	for (int j = 0; j < 9; ++j) {
		for (int k = 3 << j; k < 1024; ++k)
			if (k & (1 << j) && k & (1 << (j + 1))) cnt[k] = -1;
	}
	for (int k = 1; k < 1024; ++k) {
		if (cnt[k] < 0) continue;
		for (int j = 0; j < 10; ++j) if (k & (1 << j)) cnt[k]++;
	}

* cnt배열을 구해놓지 않으면 행을 처리할 때 마다 위 연산을 반복해야해 굉장히 불편하다.

 

 

 

1. 입력

교실 정보는 학생이 앉을 수 없는 자리의 bit를 1로 해 각 행의 정보를 배열 b에 저장한다.

b[ i ]  i행의 상태 (0≤i＜N)

	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i) {
		scanf("%s", &tmp);
		b[i] = 0;
		for (int j = 0; j < M; ++j) if (tmp[j] == 'x') b[i] |= (1 << j);
	}

 

 

 

2. dp배열 구하기

이후 cnt배열을 이용해 dp를 채운다.

dp[ i ][ k ]  i행의 상태가 k일 때 앉을 수 있는 학생 수의 최댓값 (0≤i＜N, 0≤k＜2^M)

 

이때 아래에 주의한다.

• b[ i ] & k ≥0  ⇒ i행이 k인 상태가 불가능하다. 고려하지 않는다.
• cnt[ k ] ＜0  ⇒ k는 아예 불가능한 상태이다. 고려하지 않는다.

 

i행에 대해 k가 가능한 상태이면 i-1행의 상태에 따라 dp[ i ][ k ]를 구한다. i-1행의 상태를 up이라 하면

• cnt[ up | k ] ＜0  ⇒ i행의 상태가 k일 때 i-1행의 상태가 up이면 컨닝을 할 수 있다.
• 가능한 up에 대해 dp[ i-1 ][ up ]이 가장 큰 경우를 선택한다.

* 그림에서 초록색은 가능, 남색은 불가능한 경우

   연속한 행의 상태를 OR연산했을 때 불가능한 상태(cnt＜0)이면 한 명이라도 대각선으로 컨닝할 수 있다는 의미이다.

* 위 그림에서 dp[ 1 ][ 4 ] = dp[ 0 ][ 5 ] + cnt[ 4 ] = 3 이다.

 

이 과정 코드는 아래와 같다.

line 1~4: 0행의 경우 위 행을 고려할 필요 없으니 따로 처리한다.

line 5~~: 1행~N-1행은 위 행을 고려하며 for문으로 처리한다.

	for (int k = 0; k < (1 << M); ++k) {
		if ((b[0] & k) || cnt[k] < 0) continue;
		dp[0][k] = cnt[k];
	}
	for (int i = 1; i < N; ++i) {
		for (int k = 0; k < (1 << M); ++k) {
			if ((b[i] & k) || cnt[k] < 0) continue;

			int upcnt = 0;
			for (int up = 0; up < (1 << M); ++up) {
				if (cnt[up | k] >= 0) upcnt = max(upcnt, dp[i - 1][up]);
			}
			dp[i][k] = cnt[k] + upcnt;
		}
	}

 

마지막 행에서 최댓값을 찾으면 된다.

 

 

 

---

 

 

 

 

 

#include <cstdio>
#include <algorithm>
using namespace std;

int dp[10][1024];
int main() {
	int cnt[1024] = { 0, };
	for (int j = 0; j < 9; ++j) {
		for (int k = 3 << j; k < 1024; ++k)
			if (k & (1 << j) && k & (1 << (j + 1))) cnt[k] = -1;
	}
	for (int k = 1; k < 1024; ++k) {
		if (cnt[k] < 0) continue;
		for (int j = 0; j < 10; ++j) if (k & (1 << j)) cnt[k]++;
	}
	
	char tmp[11];
	int T, N, M;
	int b[10] = { 0, };
	
	scanf("%d", &T);
	while (T--) {
    	// Get Input
		scanf("%d%d", &N, &M);
		for (int i = 0; i < N; ++i) {
			scanf("%s", &tmp);
			b[i] = 0;
			for (int j = 0; j < M; ++j) if (tmp[j] == 'x') b[i] |= (1 << j);
		}

		// Get DP
		for (int k = 0; k < (1 << M); ++k) {	//row 0
			if ((b[0] & k) || cnt[k] < 0) continue;
			dp[0][k] = cnt[k];
		}
		for (int i = 1; i < N; ++i) {			//row 1 ~ N-1
			for (int k = 0; k < (1 << M); ++k) {
				if ((b[i] & k) || cnt[k] < 0) continue;

				int upcnt = 0;
				for (int up = 0; up < (1 << M); ++up) {
					if (cnt[up | k] >= 0) upcnt = max(upcnt, dp[i - 1][up]);
				}
				dp[i][k] = cnt[k] + upcnt;
			}
		}

		// Get ANS from row N-1
		int ans = 0;
		for (int i = 0; i < N; ++i) {
			for (int k = 0; k < (1 << M); ++k) ans = max(ans, dp[i][k]);
		}
		printf("%d\n", ans);

		// Initialize DP (for the next case)
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < (1 << M); ++j) dp[i][j] = 0;
		}
	}
	return 0;
}

 

처음에는 14939번 불끄기 처럼 생각했으나