BOJ 1285 : 동전 뒤집기

문제링크

풀이요약

그리디, 비트마스킹 (답안 참조)

풀이상세

1. 문제는 최소의 T 의 경우를 구하는 문제이다. 나의 경우 비트마스킹을 진행하기 위해 입력값을 int 형태로 받았다. 예를 들어 TTH 의 경우면 3, HHT 의 경우는 4 이다. 이진법의 자리로 판단하는 경우 T 가 있다면 그만큼 int 값으로 더했다.

2. 행에 대한 모든 부분 집합을 구한다. 나오는 부분집합은 행 뒤집기를 진행한다.

3. 행을 뒤집은 임의의 경우의 수에서 열의 T 의 개수를 구한다. 열을 현재 상태로 두냐 안 두냐의 차이이다. 예를들어, N=5 이며 현재 행이 HHTTH 라면 이번 행은 뒤집지 않는 것이 맞다. (뒤집으면 T 는 3개가 되며, 최소 T 와 멀어진다.)

4. 즉 뒤집지 않은 열의 T 의 갯수와 뒤집은 열의 T 의 갯수 중 최소의 값을 더해가며 현재 열의 경우의 수에서 나오는 최소의 T 의 갯수를 구하여 정답에 반영한다. (뒤집지 않은 열의 T 의 갯수가 a 인 경우, 뒤집은 열의 T 의 갯수는 N-T 이다.

느낀점

• 이론으로는 알겠으나, 늘 구현이 어렵다.

#include <iostream>
#include <vector>
using namespace std;
int N, a[24], ans = 401;
void input() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> N;
    string s;
    for (int i = 0; i < N; i++) {
        cin >> s;
        for (int j = 0; j < N; j++) {
            if (s[j] == 'T') a[i] += (1 << j);
        }
    }
}

void solve(int d) {
    if (d >= N) {
        int t = 0;
        for (int i = 1; i <= (1 << (N - 1)); i *= 2) {
            int c = 0;
            for (int j = 0; j < N; j++) if (a[j] & i) c++;
            t += min(c, N - c);
        }
        ans = min(ans, t);
        return;
    }

    solve(d + 1);
    a[d] = ~a[d];
    solve(d + 1);
}

void output() {
    cout << ans;
}

int main() {
    input();
    solve(0);
    output();
}