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번 불끄기 처럼 생각했으나
'Probelm Solving > BOJ' 카테고리의 다른 글
BOJ3830 교수님은 기다리지 않는다 (0) | 2021.06.19 |
---|---|
BOJ1949 우수 마을 (0) | 2021.06.10 |
BOJ3716 도로 네트워크 (0) | 2021.04.23 |
BOJ1086 박성원 (0) | 2021.04.21 |
BOJ13141 Ignition (0) | 2021.03.17 |
댓글