[백준 1285] 동전 뒤집기

 \( N \leq 20\)이므로 \(2^N\) 또는 그에 준하는 풀이를 생각해볼 만하다.

 가로 \(N\)개의 줄, 세로 \(N\)개 줄 중 무엇을 뒤집을 것인지 생각하는 문제이므로 존재할 수 있는 선택의 개수는 \(2^{2N}\)이다. 그중에서 가로줄과 세로줄 중 하나가 몇 번 줄을 뒤집을지 그 상태가 이미 정해졌다면(편의상 세로줄이라 하겠다), 가로줄에 H가 더 많으면 가만히 놔두는 것을 선택하고 T가 더 많으면 뒤집는 것을 선택하는 그리디 알고리즘을 생각할 수 있다. 이것이 성립하는 이유는 세로줄이 이미 선택된 이상 모든 가로줄은 서로 영향을 주지 않는 독립이므로 순간의 최적 선택이 전체 최적 선택을 담보하기 때문이다.

 한 번 그리디 알고리즘을 시행할 때마다 전체 셀 개수인 \(O(N^2)\)의 시간복잡도를 소요한다. 따라서 모든 세로줄에 대해 브루트포스를 하고 각각의 경우에 대해 그리디 알고리즘을 돌리면 \(O(N^2 \times 2^N)\)에 문제를 풀 수 있다.

 

#include <bits/stdc++.h>

char rev(char x) {
    return 'H' + 'T' - x;
}

int get_min(const std::string& s) {
    return (int) std::min(std::count(s.begin(), s.end(), 'H'), std::count(s.begin(), s.end(), 'T'));
}

int min_case(std::vector<std::string> vec, int mask) {
    int n = vec.size();
    for (int j = 0; j < n; ++j) {
        if (mask & (1 << j)) {
            for (int i = 0; i < n; ++i) {
                vec[i][j] = rev(vec[i][j]);
            }
        }
    }
    int ret = 0;
    for (const auto& s : vec) {
        ret += get_min(s);
    }
    return ret;
}

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<std::string> vec(n);
    for (auto& s : vec) std::cin >> s;
    
    int ret = n * n;
    for (int i = 0; i < (1 << n); ++i) {
        ret = std::min(ret, min_case(vec, i));
    }
    
    std::cout << ret << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}

 

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

1285번: 동전 뒤집기