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

풀이

• 모든 경우의 수를 따지면서 뒷면으로 된 동전의 최소값을 찾는 문제이다.
• 비트마스킹을 활용하면 비교적 간편하게 모든 경우의 수를 확인할 수 있다.

1. 행 뒤집기

• 백준 문제에 업로드 되어있는 그림이다. 위쪽부터 순서대로 1, 2, 3행이라 했을 때 행을 뒤집을 수 있는 경우의 수는 다음과 같다.

1. 하나도 뒤집지 않는다.
2. 1행만 뒤집는다.
3. 2행만 뒤집는다.
4. 3행만 뒤집는다.
5. 1행, 2행을 뒤집는다.
6. 1행, 3행을 뒤집는다.
7. 2행, 3행을 뒤집는다.
8. 모두 뒤집는다.

• 즉 경우의수는 2^n개가 됨을 알 수 있으며, 이를 비트마스크로 간편하게 할 수 있다. 비트마스크를 모른다면 아래 게시글을 참조하자

14391. 종이 조각 (파이썬)

• 위 이진수 표에서 1일 때 행을 뒤집고, 0일 때 행을 뒤집지 않는 것으로 표현하면 모든 경우의 수를 확인할 수 있다.
• 즉 range(2 ** N) 또는 range(1 << N)을 통해 모든 경우의 수를 확인할 수 있다.

2. 열을 확인하며 개수 세기

• 위 그림은 첫 그림에서 첫번째 행을 뒤집은 경우이다.
• 이제 각 열에대해 for loop을 돌면서 해당 열을 뒤집었을 때와 뒤집지 않았을 때 각각의 뒷면 수를 세어 최소값을 구하면 된다.

• 먼저 첫번째 열에서 뒷면의 개수는 3개이다. 만약 이 열을 뒤집는 다면 뒷면의 개수는 N-3 = 0개가 될 것이다.
• 최소값은 0이므로 Total은 여전히 0이다.

• 두번째 열에서는 뒷면의 개수는 1개, 뒤집는다면 N-1 = 2개이다.
• 최소값은 1이므로 Total = 0 + 1 = 1이된다.

• 마지막 열에서는 뒷면의 개수는 1개, 뒤집는다면 N-1 = 2개이다.
• 최소값은 1이므로 Total = 1 + 1 = 2가된다.

이런식로 모든 경우의 수에 대해 Total을 구하면, 그 최소값이 정답이 된다.

코드

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(str, input().rstrip())) for _ in range(N)]

answer = 2147000000

# 1. 행이 뒤집힌 배열 생성
board_reversed = [["H"] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if board_reversed[i][j] == board[i][j]:
            board_reversed[i][j] = "T"
# 2. 비트마스크로 경우의 수 탐색
for case in range(1 << N):
    board_temp = []
    for i in range(N):
        if case & (1 << i):
            board_temp.append(board_reversed[i])
        else:
            board_temp.append(board[i])
    # 3. 열방향 탐색으로 뒤집는 것과 안뒤집는 것중 최대값 저장
    total_count = 0
    for j in range(N):
        count = 0
        for i in range(N):
            if board_temp[i][j] == "T":
                count += 1
        total_count += min(count, N-count)
    # 4. 현재 답보다 작다면 최소값이므로 저장
    answer = min(answer, total_count)

print(answer)

코멘트

시간 초과

• 이 문제에서 N의 범위는 20이므로, 최대 O(2^20)의 시간 복잡도를 갖는다.
• 때문에 Python 3로 문제를 풀 경우 시간초과가 나며 PyPy3로 제출하여 풀었다.
• 물론 이를 잘 최적화해서 보다 적은 시간복잡도로 푸는 방법도 존재하는 것 같지만, 너무 토끼굴로 들어가는 것 같아 거기까지는 확인하지 못했다.

소감

• 이 문제처럼 경우의 수를 따져가며 모두 확인해야하는 경우 비트마스크가 유용함을 알 수 있었다.
• 처음엔 브루트포스로 풀어야한다는 것도 몰라서 다른 방법을 찾아 헤매었다. 왜 문제를 처음 마주치면 브루트포스 또는 그리디를 먼저 체크하라는 지 알 수 있었다.