[백준(BOJ)] #1285- 동전 뒤집기 (파이썬, PyPy3)

문제

 

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

1285번: 동전 뒤집기

---

문제 풀이

 

 저는 이 문제를 해결하기 위해 먼저 행 또는 열을 기준으로 선택하여 뒤집는 모든 경우의 수를 구했습니다. 이때 행을 뒤집는 연산을 할 때 비트마스킹을 적용하여 행을 뒤집는 경우의 수를 구했습니다.

 

2022.07.15 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] 비트마스크(BitMask)

[파이썬으로 배우는 알고리즘] 비트마스크(BitMask)

 

그렇다면 어떻게 비트마스킹을 적용시켜서 행을 뒤집을 수 있을까요?

각 행을 뒤집은 경우를 1, 뒤집지 않은 경우를 0, n의 크기를 3이라고 예를 들면 각 행을 뒤집는 경우의 수를 다음과 같이 이진수로 표현할 수 있습니다.

 

	0	1	2	3	4	5	6	7
이진수	000	001	010	011	100	101	110	111
뒤집은 행	x	1행	2행	1, 2행	3행	1, 3행	2, 3행	1, 2, 3행

이렇게 2^n 가지 경우의 수를 갖게 되고, 행을 뒤집고 나서 이번엔 열을 기준으로도 순회를 해주며 뒤집어 줘야 합니다. 각 열에서 뒷 면의 개수가 더 많으면 n에서 뒷 면의 개수를 뺀 값을 뒷 면의 개수로 하여 뒤집은 걸로 적용시킵니다.

 

풀이 과정

1) 아무 행도 뒤집지 않은 경우. 열 순회 시 1열과 3열이 T가 더 많으므로 뒤집어 줌. 뒷면의 총 개수는 2개

 

2) 1행을 뒤집은 경우. 열 순회 시 1열이 T가 더많으므로 뒤집어 줌. 뒷면의 총 개수는 2개

 

3) 2행을 뒤집은 경우. 열 순회시 3열이 T가 더 많으므로 뒤집어 줌. 뒷면의 총 개수는 2개

 

4) 1, 2행을 뒤집은 경우. 열 순회시 1, 2, 3열이 T가 더 많으므로 뒤집어 줌. 뒷면의 총 개수는 3개

 

5) 3행을 뒤집은 경우. 열 순회시 T가 더 많은 경우는 없으므로 뒤집지 않음. 뒷면의 총 개수는 3개

 

6) 1, 3 행을 뒤집은 경우. 열 순회시 1, 2열이 T가 더 많으므로 뒤집어 줌. 뒷면의 총 개수 2개

 

7) 1, 2, 3 행을 뒤집은 경우. 열 순회시 2열이 T가 더 많으므로 뒤집어 줌. 뒷면의 총 개수 2개

 

8) 최솟값으로 뒷면의 총개수는 2 개

 

---

구현

코드

n = int(input())
coin = [list(input()) for _ in range(n)]
res = n * n + 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'

    tsum = 0
    for i in range(n):
        cnt = 0
        for j in range(n):
            if tmp[j][i] == 'T':
                cnt += 1
        #T가 더 많을 경우 뒤집기
        tsum += min(cnt, n-cnt)
    res = min(res, tsum)

 

결과