[BOJ 1285] 동전 뒤집기

1285번: 동전 뒤집기

 

문제 설명

뒷면이 위를 향하는 동전 개수를 최소로 해야 하니 T가 최소일 때를 T의 개수를 구해야 한다.

 

예제 설명

위 그림처럼 2번째 행을 뒤집고 > 3번째 열을 뒤집으면 T가 2개가 되는데 이 때가 T가 최소일 때이므로 2가 출력된다

 

시간 복잡도

N은 최대 20까지 가능하며, 행이나 열을 뒤집을 수 있기 때문에 모든 경우의 수를 생각했을 때 총 연산 횟수는 2^(20+20) = 2^40번일 것이다.

2^40번이라면 시간 초과가 날 것이다.

 

하지만, 이 때 행만 뒤집으면 열은 뒤집을지 말지가 정해지기 때문에 행을 뒤집는 경우만 연산을 하여 2^40을 2^20으로 줄일 수 있다.

왼쪽과 같은 동전 배열에서 1번째 행을 뒤집으면 오른쪽과 같은 배열이 만들어진다.

이 때 1번째 열을 뒤집는 경우와 뒤집지 않는 경우 둘로 경우의 수를 분기하지 않아도 된다.

1번째 열에서 T의 개수가 N의 개수보다 많기 때문에 T를 최소로 만들려면 1번째 열을 뒤집는 경우만 보면 된다.

 

구현 아이디어

• 상태가 H, T 2가지이기 때문에 비트마스킹을 사용할 수 있다.
• 뒤집는 것을 구현할 때는 ~연산을 사용할 수 있다.
• 행을 기준으로 T의 개수를 생각한다. (열 뒤집기 여부는 자동 결정)

 

코드 구현

1. 입력을 받아 한 행을 수로 표현한다.

ex) HTT = 011 = 2 + 4 = 6

for (int i = 1; i <= n; ++i) {
    string s;
    int temp = 1;

    cin >> s;
    for (int j = 0; j < n; ++j) {
        // H = 0, T = 1로 하여 한 행을 자연수로 표현한다.
        if (s[j] == 'T') a[i] |= temp;
        temp *= 2;
    }
}

a 배열은 각 행을 정수로 표현한 배열로 처음에는 0으로 초기화된 상태이다.

a 배열의 예시

만약 i=0이고 s = "HTT"일 때,

j	a[i]	temp
0	0	2 (10)
1	00 | 10 = 10	4 (100)
2	010 | 100 = 110	8 (1000)

이 되어 a[0] = 110이다.

 

2. DFS(재귀)를 돌며 각 경우에 대해 T의 개수를 구하며 최소 개수를 갱신한다.

void go(int here) {
    if (here == n+1) { // 마지막 행까지 탐색을 완료했을 때
        int sum = 0; // T의 개수
        for (int i = 1; i <= (1 << (n-1)) ; i*= 2) { // 각 열에 대하여 (1, 2, 4 ...)
            int cnt = 0; // 각 행의 T의 개수
            for (int j = 1; j <= n; ++j) { // 각 행을 체크
                if (a[j] & i) cnt ++; // 임의의 열에서 T의 개수를 저장
            }
            // T와 N의 개수 중 작은 쪽을 sum에 더한다
            // N의 개수를 더한다 = 열을 뒤집는다
            sum += min(cnt, n - cnt);
        }
        ret = min(ret, sum);
        return;
    }

    go(here+1); // 뒤집지 않고 다음 행으로 이동
    a[here] = ~a[here]; // 행을 뒤집는다
    go(here+1); // 다음 행으로 이동
}

cnt 계산 과정 예시 (i=1)

전체 코드

#include <bits/stdc++.h>

using namespace std;

#define INF 987654321
int n; // 한 행(열)에 놓인 동전의 수
int a[24]; // 각 행을 정수로 표현
int ret = INF; // 동전의 최소 개수

void go(int here) {
    if (here == n+1) { // 마지막 행까지 탐색을 완료했을 때
        int sum = 0; // T의 개수
        for (int i = 1; i <= (1 << (n-1)) ; i*= 2) { // 각 열을 2의 제곱으로 생각 (1, 2, 4 ...)
            int cnt = 0; // 각 행의 T의 개수
            for (int j = 1; j <= n; ++j) { // 각 행을 체크
                if (a[j] & i) cnt ++; // 임의의 열에서 T의 개수를 저장
            }
            // T와 N의 개수 중 작은 쪽을 sum에 더한다
            // N의 개수를 더한다 = 열을 뒤집는다
            sum += min(cnt, n - cnt);
        }
        ret = min(ret, sum);
        return;
    }

    go(here+1); // 뒤집지 않고 다음 행으로 이동
    a[here] = ~a[here]; // 행을 뒤집는다
    go(here+1); // 다음 행으로 이동
}

int main() {

    cin >> n;

    for (int i = 1; i <= n; ++i) {
        string s;
        int temp = 1;

        cin >> s;
        for (int j = 0; j < n; ++j) {
            // H = 0, T = 1로 하여 한 행을 자연수로 표현한다.
            if (s[j] == 'T') a[i] |= temp;
            temp *= 2;
        }
    }

    go(1);
    cout << ret << "\n";

    return 0;
}