[BAE/<JOON> 문제풀이] 1014. 컨닝

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

1014번: 컨닝

서론

번호 순으로 풀 때 초라기에 이어 2번째로 등장하는 보스몹 문제다.

풀이에 비해 티어가 과하게 높게 책정된 것 같다. 기믹이 딱 골드1 스럽다. 그 점 3개 골라서 삼각형 만드는 문제랑 거의 똑같다고 생각한다. 그동안 풀었던 플레 문제중 가장 빨리 풀었다. 문제 독해부터 AC까지 1시간 정도 걸린것 같다. (OUO) V

---

풀이

k번째 행의 배치를 정해놓고 최종적으로 n행까지 진행했을 때 정해지는 최대 학생 수와 1대1 대응이다. k번째 행의 배치 제한이 정해졌다면 k행부터 n행까지 배치할 수 있는 최대 학생 수는 변하지 않는다. 한 행의 한 배치에 대해서 2번 이상 탐색할 필요가 없다. 따라서 행과 배치를 결합한 DP 테이블을 만들어 중복인 경우를 제외하며 계산할 수 있다.

점화식은 아래와 같다.

• DP[행][배치(bitmask)] = 해당 행에서 해당 배치로 학생을 배치했을 때 계산되는 최대 배치 학생 수
• DP[row][state] = max(DP[row + 1][새로생성한배치] + 현재 행에 추가한 학생 수)

풀이 로직을 상세하게 나열하면 아래와 같다.

1. 현재 배치에서 학생을 배치할 수 있는 위치를 찾아낸다.

2. 가능한 모든 학생 배치에 대해 ( 2^위치수 ) 조건에 만족하는 배치를 찾아낸다.
 : 배치할 때는 옆자리만 검사하고 대각선 배치 제한은 다음 배치 제한에 추가하여 전달한다. 또한 배치 제한은 양방이므로 행 제한을 검사할 때 각 학생들의 왼쪽만 검사해도 상관없다.

---

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
using namespace std;
using ll = long long;
int n, m;
vector<vector<int>> arr, dp, ch;
int r(int row, int st) {
    if (row > n) return 0;
    int& ret = dp[row][st];
    if (ret != -1) return ret;
    ret = 0;
    vector<int> fp;
    for (int i = 0; i < m; i++) {
        if (((1 << i) & st) == 0 && arr[row][i + 1] == 0) {
            fp.push_back(i);
        }
    }
    for (int i = 0; i < (1 << fp.size()); i++) {
        vector<int> cp(m + 1); bool si = false; int nxp = 0; int ads = 0;
        for (int j = 0; j < fp.size(); j++) {
            if (((1 << j) & i) > 0) {
                if (fp[j] > 0 && cp[fp[j] - 1] == 1) { // 한쪽만 체크해도 됨 ㅇㅇ;
                    si = true;
                    break;
                }
                cp[fp[j]] = 1;
                ads++;
                if (fp[j] > 0) {
                    nxp |= (1 << (fp[j] - 1));
                }
                if (fp[j] < m - 1) {
                    nxp |= (1 << (fp[j] + 1));
                }
            }
        }
        if (si == true) continue;
        int s1 = r(row + 1, nxp) + ads; ret = ret > s1 ? ret : s1;
    }
    return ret;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tc; cin >> tc;
    while (tc--) {
        cin >> n >> m; arr = ch = vector<vector<int>>(n + 1, vector<int>(m + 1)); dp = vector<vector<int>>(n + 1, vector<int>(1 << m, -1));
        for (int i = 1; i <= n; i++) {
            string s; cin >> s;
            for (int j = 1; j <= m; j++) {
                if (s[j - 1] == '.') {
                    arr[i][j] = 0;
                }
                else {
                    arr[i][j] = 1;
                }
            }
        }
        cout << r(1, 0) << "\n";
    }
    return 0;
}