2022.04.25 [백준] (python 파이썬) 동전 뒤집기

 

 

 

 

 

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

1285번: 동전 뒤집기

---

풀이

이 문제는 열 또는 행의 동전을 뒤집었을 때와 뒤집지 않았을 때의 뒷면 T의 최소 갯수를 구하는 문제이다.

위의 설명에서 보면 2가지 경우가 있다. 그래서 비트마스킹으로 각 행에대해 뒤집냐 뒤집지않냐를 고려해줄것이다.

예를 들면 (110)이면 1, 2행을 뒤집고 3행은 뒤집지않는 경우를 고려한다는 말이다.

 

1. 먼저 T개수의 최소값을 저장할 ans변수를 생성해준다. 여기서 값을 n*n으로 해준 이유는 최소값을 구하는 문제이기 때문에 초기값을 최대값으로 설정해야 하기 때문이다.
2. for문을 이용하여 각 행에대해 뒤집을지 말지를 비트값으로 돌며 확인한다. 
   예를 들어 n이 3이라고하면 비트값은 000, 001, 010, 011 ········111까지 총 8가지 경우를 확인할 수 있다.
3. 새로운 동전 배열인 tmp를 만들어 슬라이싱을 이용해 초기의 배열을 복사해준다.
   만약 초기배열인 arr배열을 그대로 사용하면 처음의 경우를 확인한 후, 다음의 경우를 확인하지 못하기 때문이다.
   그래서 각 경우의 수마다 초기의 배열을 복사하여 사용한다.
4. 10번째줄에서 for문을 돌려 비트값의 각 자리수에 1이 있는지 확인하고 만약 1이 있으면 해당 행의 동전을 모두 뒤집어준다. 비트값의 자리수가 1이면 해당 행을 뒤집어 준다는 의미이기 때문이다.
5. 해당 비트값을 이용해 행을 뒤집어 주었으면 이제 열을 확인한다.
   1. 17번째의 줄의 cnt는 해당 경우의 수에 T의 총 갯수를 저장할 변수이다.
   2. 이후 행을 확인할 for문을 돌리고 각 열에 대해 T의 갯수를 저장할 cnt_t를 생성한다.
   3. 열을 확인할 for문을 돌리고 각 열에 대해 T의 갯수를 cnt_t에 저장한다.
   4. 각 열을 모두 확인 할 때마다 cnt에 cnt_t와 (n-cnt_t)를 비교하여 작은 값을 더한다.
      이유는 cnt_t가 작으면 해당 열은 뒤집지 않고 크면 뒤집어 T의 갯수를 최소화 하기 위해서 이다.
      1. 해당 비트값에 대해 행과 열을 모두 확인하면 ans에 해당 경우의수에 대해 총 T의 갯수 cnt와 ans값을 비교하여 최소값을 저장한다.

 

n=int(input())
arr=[]
for _ in range(n):
    arr.append(list(input()))
 
ans=n*n
 
for bit in range(1<<n):
    tmp=[arr[i][:] for i in range(n)]
    for i in range(n):
        if bit & (1<<i):
            for j in range(n):
                if tmp[i][j]=='T':
                    tmp[i][j]='H'
                else:
                    tmp[i][j]='T'
    cnt=0
    for i in range(n):
        cnt_t=0
        for j in range(n):
            if tmp[j][i]=='T':
                cnt_t+=1
        cnt+=min(cnt_t,n-cnt_t)
    ans=min(cnt,ans)
 
print(ans)