[BOJ] 백준 1014 - 컨닝

문제 링크

www.acmicpc.net/problem/1014

1014번: 컨닝

 

풀이

각 줄마다 사람을 앉힐 수 있는 각 조합을 상태로 생각합니다.

 

맨 앞줄부터 사람을 채워나간다고 합시다.

 

$d[i][s]$: $i$번 줄에 조합 $s$로 사람을 앉힐 때 현재까지 앉을 수 있는 사람의 최댓값.

조합 $s$를 비트마스킹으로 관리할 수 있습니다.

 

어떤 자리에 사람을 앉히려고 할 때, 그사람의 바로 앞줄 대각선과 바로 옆에만 사람이 없으면 앉을 수 있습니다.

따라서 단순하게 위의 조건을 만족시키는 두 조합에 대해, ($i$번째 줄에 사람을 앉히는 모든 조합) $\times$ ($i-1$번째 줄에 사람을 앉히는 모든 조합)을 모두 살펴보면 됩니다.

$d[i][$현재 조합$]$ = $max(d[i-1][$유효한 모든 조합$])$ + (현재 조합으로 앉힐 수 있는 사람의 수)

 

간단한 풀이에 흉측한 코드가 나오네요...

 

정답 코드

#include <bits/stdc++.h>
using namespace std;

int t;
int n, m;
int d[22][1 << 11];
string p[22];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t;
    while (t--) {
        memset(d, 0, sizeof(d));
        cin >> n >> m;
        p[0] = "                    ";
        for (int i = 1; i < n + 1; i++) {
            cin >> p[i];
        }
        int ans = 0;

        for (int i = 1; i < n + 1; i++) {
            for (int comb1 = 0; comb1 < (1 << m); comb1++) {
                int now = 0;
                bool c = false;
                int cnt = 0;
                for (int j = 0; j < m; j++) {
                    // comb1의 비트 확인
                    if (comb1 & (1 << j)) {
                        cnt++;
                        if (p[i][j] == 'x' || (j > 0 && (comb1 & (1 << (j - 1))))) {
                            // comb1 자체가 유효하지 않은 조합일 경우
                            c = true;
                            break;
                        }
                        now |= (1 << j);
                    }
                }
                if (c) continue; // 유효하지 않은 comb1
                for (int comb2 = 0; comb2 < (1 << m); comb2++) {
                    int prev = 0;
                    bool c2 = false;

                    for (int k = 0; k < m; k++) {
                        // comb2의 비트 확인
                        if (comb2 & (1 << k)) {
                            if (p[i - 1][k] == 'x' || (k > 0 && (comb2 & (1 << (k - 1))))) {
                                // comb2 자체가 유효하지 않은 조합일 경우
                                c2 = true;
                                break;
                            }
                            prev |= (1 << k);

                            // now와 prev의 관계가 유효한지 확인
                            if (k - 1 >= 0 && (now & (1 << (k - 1)))) {
                                c2 = true;
                                break;
                            }
                            if (k + 1 < m && (now & (1 << (k + 1)))) {
                                c2 = true;
                                break;
                            }
                        }
                    }
                    if (c2) continue; // 유효하지 않은 comb2

                    d[i][now] = max(d[i][now], d[i - 1][prev] + cnt);
                    ans = max(ans, d[i][now]);
                }
            }
        }
        cout << ans << '\n';
    }
}