[백준] 1285 동전 뒤집기 python(pypy)

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

1285번: 동전 뒤집기

import sys; input = sys.stdin.readline
n = int(input())
coin = [[False] * n for _ in range(n)]
cnt = 401 # 최대값이 20*20 /2 인데 그냥 계산하기 편하게 400 + 1
# head: 0, tail: 1
for i in range(n):
    tmp = input()
    for j in range(n):
        if tmp[j] == 'T':
            coin[i][j] = True

# bit = (1 << n) - 1
for bit in range(1 << n):
    new_coin = [[False] * n for _ in range(n)]
    # deep copy
    for i in range(n):
        for j in range(n):
            new_coin[i][j] = coin[i][j]
    # 행을 뒤집는 경우를 완전 탐색(근데 bit를 곁들인)
    for i in range(n):
        if bit & (1 << i):
            for j in range(n):
                new_coin[i][j] = not new_coin[i][j]
    # 각 열에 대해 뒤집는경우와 뒤집지 않는 경우를 판단하여, T가 적은쪽으로 열을 뒤집음
    cmpcnt = 0
    for i in range(n):
        f, b = 0, 0
        for j in range(n):
            if new_coin[j][i]:
                f += 1
            else:
                b += 1
        cmpcnt += (b if f > b else f)
    if cnt > cmpcnt :
        cnt = cmpcnt
    # bit -= 1
print(cnt)

행 뒤집으면서 하는건 알겠는데 어떻게 짜야할지 모르겠다.

직접 시뮬레이션처럼 돌리는 경우 시간초과가 난다.

 

그래서 아래 블로그를 베껴서 제출했는데 봐도 무슨 말인지 모르겠다.

bit를 사용하여 모든 경우를 구하는데 행을 뒤집는 것을 먼저 구하고 열을 뒤집는다.

열을 뒤집을땐 H가 많이 보이는 쪽을 선택하게된다.

여기에서 궁금한점은 모든 행, 열에 대해서 한번씩만 뒤집어서 값을 찾는데 이렇게 하면 왜 최소값이 나오는지 이해가 가지않는다. 열을 뒤집은 이후 다시 행을 뒤집을때 최소값이 나올수도 있지 않을까?

직접 돌려보니 열을 뒤집은 이후 다시 행을 뒤집을때 최소값이 나오는 경우 다른 곳에서 중복이 된다.

3
THH
HTT
TTT

bit 0 
[[True, False, False],
 [False, True, True],
 [True, True, True]]
bit 1
 [[False, True, True],
 [False, True, True],
 [True, True, True]]
bit 2
 [[True, False, False],
 [True, False, False],
 [True, True, True]]
bit 3
 [[False, True, True],
 [True, False, False],
 [True, True, True]]
bit 4
 [[True, False, False],
 [False, True, True],
 [False, False, False]]
bit 5
 [[False, True, True],
 [False, True, True],
 [False, False, False]]
bit 6
 [[True, False, False],
 [True, False, False],
 [False, False, False]]
bit 7
 [[False, True, True],
 [True, False, False],
 [False, False, False]]

 

 

https://nicotina04.tistory.com/33

백준 1285 - 동전 뒤집기