백준 13573 - 동전 뒤집기 3

step 1

임의의 행이나 열을 기준으로 뒤집거나, 그대로 두거나 둘 중 하나의 경우만 고려하면 됩니다. 두 번 뒤집는 경우는 신경쓰지 않아도 됩니다.

$N$이 20 이하인 것에 집중합니다. 각 행에 대해서 뒤집을지 말지가 정해지면 그때부터는 세로줄만 뒤집으면 됩니다.

"각 행에 대해서 뒤집을지 말지"는 2진수로 표현할 수 있습니다. $N$이 5라고 할 때 하나도 뒤집지 않은 것은 $00000_{(2)}$, 첫번째 행만 뒤집는 것은 $00001_{(2)}$로 표현할 수 있습니다. 이 숫자를 행의 상태라고 합시다.

모든 행의 상태에 대해서, 각 열의 앞면 동전의 개수를 알 수 있다면 해당 열을 뒤집을지 말지도 정할 수 있고 최종 답을 구할 수 있습니다.

 

step 2

SOS DP(https://codestudycafe.tistory.com/6)에 있는 아이디어 일부를 가져올 것입니다.

 

$DP[i][j]$ = 행의 상태 가 $i$일 때 $i$에 해당하는 그룹 내에 있는 숫자들 중 1(앞면)의 개수가 $j$인 수의 개수

 

뭔소린가 싶긴 한데 예제 입력 2에 있는 예시를 이용해서 천천히 살펴봅시다.

3 4
HTTH
THTH
HTTT

H를 1, T를 0으로 생각하면 각각의 열도 2진수로 나타낼 수 있습니다. 이때, 행의 상태를 보면 첫번째 행이 2진수의 첫번째 숫자에 대응합니다. 따라서 열을 2진수로 바꿀 때 첫번째 행이 첫번째 숫자, 마지막 행이 마지막 숫자에 들어가도록 합니다. 예를 들어 네번째 열은 THH이고 2진수로 바꾸면 $011_{(2)}$입니다.

각 열을 2진수로 바꾸고 각 숫자를 해당하는 그룹에 넣는다고 상상해 봅시다. 네번째 열은 $011_{(2)}$이므로 그룹 3에 들어갑니다.

초기 상태

각 회색 원이 하나의 그룹이라고 생각해 봅시다. 첫번째 열(HTH)은 그룹 5에 있고 행의 상태가 5일 때 전부 뒷면이 됩니다. 따라서 $DP[5][0]$에 들어가게 됩니다.

 

이제 인접한 그룹끼리 묶어줍시다. 그룹 0과 1, 그룹 2와 3, 그룹 4와 5, 그룹 6과 7이 하나로 합쳐집니다.

그룹 0-1에는 숫자 0,

그룹 2-3에는 2와 3,

그룹 4-5에는 5가 있고

그룹 6-7에는 아무 숫자도 없습니다. 0과 1은 정확히 비트 1개만큼 차이가 납니다. 따라서 $dp[1][j] += dp[0][j-1]$이 됩니다. 2-3, 4-5, 6-7에 대해서도 같은 식을 적용해 줍니다.

 

계속해서 모든 그룹이 합쳐질 때 까지 진행해 줍니다.

이쯤에서 DP의 정의에 대해 생각해 봅시다.

 

$DP[i][j]$ = 행의 상태 가 $i$일 때 $i$에 해당하는 그룹 내에 있는 숫자들 중 1(앞면)의 개수가 $j$인 수의 개수

 

$i$가 3일 때를 생각해 봅시다. 3는 그룹 0-3에 포함되어 있습니다. 즉

 

$DP[2][j]$ = 0~3인 숫자들만 남긴 상태에서 행의 상태가 3일 때 1(앞면)의 개수가 $j$인 수의 개수

 

가 됩니다. 이제

 

(1) : 0~1인 숫자들만 남긴 상태에서 행의 상태가 3일 때 1(앞면)의 개수가 $j$인 수의 개수

(2) : 2~3인 숫자들만 남긴 상태에서 행의 상태가 3일 때 1(앞면)의 개수가 $j$인 수의 개수

 

로 나누어 봅시다.

(2)는 이전 상태의 $DP$에서 $DP[3]$를 그대로 가져오면 됩니다.

(1)은 숫자가 0~1밖에 없고 이 숫자를 2진수로 바꾸었을 때 두번째 수가 전부 0이므로

 

0~1인 숫자들만 남긴 상태에서 행의 상태가 1일 때 1(앞면)의 개수가 $j - 1$인 수의 개수

 

와 같습니다. 즉 $DP[1][j-1]$을 $DP[3][j]$에 더해주면 됩니다.

 

최종 상태

최종 상태는 다음과 같습니다. 열을 뒤집지 않았을 때 1의 개수가 $x$개면 열을 뒤집었을 때 1의 개수는 $n-x$개가 됩니다. 이를 이용하면 쉽게 해결할 수 있습니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#define MAX 2147483647
#include <iostream>
#include <algorithm>
using namespace std;
int st[30][100100];
int dp[30][2000000];
int main() {
    int n, m, i, j, k, ans = MAX;
    cin >> n >> m;
    scanf("%d%d", &n, &m);

    for (i = 0;i < n;i++) {
        for (j = 0;j < m;j++) {
            char x;
            cin >> x;
            st[i][j] = (x == 'H' ? 1 : 0);
        }
    }

    for (i = 0;i < m;i++) {
        int val = 0;
        for (j = n - 1;j >= 0;j--) {
            val *= 2;
            val += st[j][i];
        }
        dp[0][val]++;
    }

    for (i = 1;i < (1 << n);i <<= 1) {
        for (j = 0;j < (1 << n);j++) {
            if ((j & i) == 0) {
                for (k = n - 1;k >= 0;k--) {
                    dp[k + 1][j] += dp[k][j ^ i];
                    dp[k + 1][j ^ i] += dp[k][j];
                }
            }
        }
    }

    for (i = 0;i < (1 << n);i++) {
        int cnt = 0;
        for (j = 0;j < n;j++) {
            cnt += dp[j][i] * (min(j, n - j));
        }
        if (ans > cnt) ans = cnt;
    }
    cout << ans;
    return 0;
}