티스토리 뷰
728x90
문제 링크
풀이
각 줄마다 사람을 앉힐 수 있는 각 조합을 상태로 생각합니다.
맨 앞줄부터 사람을 채워나간다고 합시다.
$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';
}
}
728x90
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[BOJ] 백준 1006 - 습격자 초라기 (0) | 2021.03.13 |
---|---|
[BOJ] 백준 5893 - 17배 (0) | 2021.03.11 |
[BOJ] 백준 1256 사전 (0) | 2021.03.10 |
[BOJ] 백준 5582 공통 부분 문자열 (0) | 2021.03.09 |
[BOJ] 백준 14226 이모티콘 (0) | 2021.03.09 |
댓글