플립 댓 댓댓댓댓댓댓
(노래 좋은데 별로 안떴어..)

BOJ 1285 - 동전 뒤집기 링크
(2022.10.27 기준 G2)
(치팅하려는 마음 Flip!)

문제

N행 N열을 이루는 동전들이 있고 각 동전은 H(앞면)나 T(뒷면)이 위로 향하고 있다.
한 행이나 한 열을 모두 뒤집는 작업을 수행할 수 있다면, 뒷면이 위로 향하는 동전의 최소 개수 출력

알고리즘

동전의 상태는 두 가지로 나타나지고 행 아니면 열을 어떻게 뒤집냐를 모두 살펴봐야 하므로 동전의 상태 그리고 뒤집을 특정 행이나 열을 비트로 나타내어 모든 경우의 수를 확인하여 답을 구하면 된다. (브루트포스)

풀이

예제를 살펴보면 N이 3이다. 3행 3열.
그렇다면 열을 뒤집는 경우의 수는 총 8가지가 된다. 각 경우의 수를 비트로 나타내면 그림과 같이 나타난다.
만약 1번째 행에서 1, 3번째 열을 뒤집는다고 가정해보자. 'THH'가 될 것이다.
H는 0, T는 1이라면? 그리고 뒤집는 경우의 수를 비트로 나타내면?
(001) ^ (101) = (100)
결국은, 열을 뒤집는 모든 경우의 수를 비트로 나타내어 확인해서, 각 행에 xor 연산을 하여 1의 개수를 세면 되는 것이다.
여기서 잠깐. N은 100, 뒷면의 개수가 95개가 나왔다. 그렇다면 앞면의 개수는 5일 것이다.
그렇다면 95를 세어야 하는 걸까? 아니다. 그 행을 한번더 뒤집으면 뒷면의 개수가 5인 것이다.
결국은 앞면의 개수와 뒷면의 개수 중 적은 것을 넣으면 되는 것이다.

위와 같은 과정을 열을 뒤집는 경우의 수. 즉, (1 << N) 의 경우를 전부 확인하면 되는 것이다.

코드

import sys; input = sys.stdin.readline

def solve():
    N = int(input())
    coins = [0] * N # 앞면은 0, 뒷면은 1로 나타내는 비트로 동전 상태 저장
    for i in range(N):
        for j, c in zip(range(N - 1, -1, -1), input().strip()):
            if c == 'H': # 뒷면이면 그 자리의 비트를 더해주면 된다.
                coins[i] += (1 << j)

    # 특정 열을 뒤집는 경우의 수를 전부 확인해야 한다.
    # row ^ flip = flipped row
    # 앞면의 개수가 적어도 그 행을 뒤집으면 뒷면의 개수가 적어지기 때문에
    # 앞면이든 뒷면이든 적은 개수를 세면 된다.
    answer = N * N
    for flip in range(1 << N):
        result = 0
        for i in range(N):
            T = bin(coins[i] ^ flip).count('1') # 특정 열을 뒤집었을 때의 뒷면의 개수를 세고
            result += min(T, N - T) # 앞면과 뒷면의 개수 중 적은 것을 더하자.
        answer = min(answer, result)
    print(answer)

solve()

여담

사실 이 문제 풀이는 동전 뒤집기 2 문제 풀이를 적기 위한 초석이었다.
시리즈 2탄도 가보자고!