[백준] 1285번 동전 뒤집기 - Python / 알고리즘 중급 1/3 - 그리디 알고리즘

ByungJik_Oh·2025년 6월 1일

[Baekjoon Online Judge]

목록 보기

160/244

💡 문제

N2개의 동전이 N행 N열을 이루어 탁자 위에 놓여 있다. 그 중 일부는 앞면(H)이 위를 향하도록 놓여 있고, 나머지는 뒷면(T)이 위를 향하도록 놓여 있다. <그림 1>은 N이 3일 때의 예이다.

이들 N $_2$ 개의 동전에 대하여 임의의 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 수행할 수 있다. 예를 들어 <그림 1>의 상태에서 첫 번째 열에 놓인 동전을 모두 뒤집으면 <그림 2>와 같이 되고, <그림 2>의 상태에서 첫 번째 행에 놓인 동전을 모두 뒤집으면 <그림 3>과 같이 된다.

<그림 3>의 상태에서 뒷면이 위를 향하여 놓인 동전의 개수는 두 개이다. <그림 1>의 상태에서 이와 같이 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업을 계속 수행할 때 뒷면이 위를 향하도록 놓인 동전의 개수를 2개보다 작게 만들 수는 없다.

N2개의 동전들의 초기 상태가 주어질 때, 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하는 동전 개수를 최소로 하려 한다. 이때의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위를 향하도록 놓인 경우 H, 뒷면이 위를 향하도록 놓인 경우 T로 표시되며 이들 사이에 공백은 없다.

출력

첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다.

💭 접근

이 문제는 비트마스크를 활용하여 먼저 뒤집을 행을 결정한 뒤, 그 행을 모두 뒤집고 열을 기준으로 T가 많은 열을 뒤집어 T의 최소 개수을 구하면 되는 문제이다.

먼저 첫번째 for 문의 경우

for bit in range(1 << n):

여기서 먼저 뒤집을 행을 결정한다. 이때 만약 n이 3이라면 bit는 000~111까지 모든 행을 뒤집지 않는 경우(000)부터 모든 행을 뒤집는 경우(111)까지 변하게 된다.

이후 두번째 for 문에서

for i in range(n):
        if bit & (1 << i):
            for j in range(n):

n이 3일 때 (1 << i)는 001, 010, 100으로 bit와 AND연산을 통해 1이 되는 열을 뒤집어준다. 예를 들어 bit가 101이라면 (1 << i)가 001, 100일 때 열을 뒤집는다고 볼 수 있다. (쉽게 말해 그냥 bit가 1인 열을 뒤집는 것이다.)

이후 선택한 열을 모두 뒤집었다면 행을 기준으로 T가 많은 행을 뒤집은 뒤, T의 개수를 세어준다. 이때는 또 행을 뒤집는 것이 아닌, 만약 T의 개수가 많다면 n에서 T의 개수를 빼는 방법으로 뒤집는 작업을 대체할 수 있다.

t_cnt = 0
    for i in range(n):
        cnt = 0
        for j in range(n):
            if tmp[j][i] == 'T':
                cnt += 1
        t_cnt += min(cnt, n - cnt)
    ans = min(ans, t_cnt)

이렇게 비트마스크 + 브루트포스 알고리즘을 사용하여 문제를 해결할 수 있다.

📒 코드

n = int(input())
coin = [list(input()) for _ in range(n)]
ans = n**2 + 1

for bit in range(1 << n):
    tmp = [coin[i][:] for i in range(n)]
    for i in range(n):
        if bit & (1 << i):
            for j in range(n):
                if tmp[i][j] == 'H':
                    tmp[i][j] = 'T'
                else:
                    tmp[i][j] = 'H'
    
    t_cnt = 0
    for i in range(n):
        cnt = 0
        for j in range(n):
            if tmp[j][i] == 'T':
                cnt += 1
        t_cnt += min(cnt, n - cnt)
    ans = min(ans, t_cnt)

print(ans)