[백준] 1285번 : 동전 뒤집기

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

1285번: 동전 뒤집기

해당 문제는 브루트포스 + 비트마스킹으로 문제를 해결 하였습니다.

행을 먼저 뒤집은뒤 -> 열을 뒤집어보며 최적의 개수를 구합니다.

행을 뒤집은 경우와 뒤집지 않은 모든 경우의 수를 구합니다. 2^N의 경우의수가 나오는데, 이 모든 경우의 수를 각각의 테이블을 구한다면 메모리 복잡도와, 시간복잡도로 해결 할 수 없습니다. 그래서 각 행을 뒤집었는지 뒤집지 않았는지 비트마스킹을 활용합니다.

 

모든 경우의 수를 구한뒤 각각의 열을 뒤집은상태와 뒤집지 않은 상태에서의 최소값을 계산하여 문제를 해결하였습니다.

import copy

N = int(input())
board = [] # 입력보드
for _ in range(N):
    board.append(list(str(input())))

reverseboard = copy.deepcopy(board) # 깊은 복사한다.
for i in range(N):
    for j in range(N):
        if reverseboard[i][j] == 'T': # Tail의 개수가 최적화 되어야 함으로 Tail일 경우 Head로 바꿔준다.
            reverseboard[i][j] = 'H'
        else:
            reverseboard[i][j] = 'T'       

ans = N**2
for k in range((1 << N)): # 경우의 수는 각 행이 뒤집은경우 뒤집지 않은경우 N^2 개이다. 비트마스킹으로 처리
    tempboard = []
    for i in range(N):
        if 1<<i & k :
            tempboard.append(reverseboard[i]) # 해당 행을 뒤집은 경우
        else:
            tempboard.append(board[i]) # 해당 행을 뒤집지 않은경우
            
    newans = 0
    for i in range(N):
        temp = 0
        for j in range(N):
            if tempboard[j][i] == 'T':
                temp += 1

        newans += min(temp, N- temp) # 뒤집지 않은경우, 뒤집은경우
        
    ans = min(ans, newans)
    
print(ans)