문제 링크 (opens new window)

풀이

1. 비트마스킹을 통해 각 행에 T 면인 경우 비트를 켜는 것으로 생각한다.

===from===
HHT
THH
THT
==========

===to===
001 => 4
100 => 1
101 => 1 + 4
========

2. 각 행을 정수 값으로 변환한다.
3. 행을 뒤집는 모든 경우의 수에 따라 열을 뒤집는 최적해는 자동으로 결정된다.
4. go 함수 실행
5. 첫 번째 go(here + 1)에서 안뒤집힌 here 행 값을 기준으로 go 재귀 진행
6. 현재 행 뒤집기
7. 뒤집어진 현재 행 기준으로 go(here+1)재귀
8. here값이 기저사례에 도달한 경우 T 갯수 체크
9. 숫자 2는 10이고, 숫자 4는 100... 즉 while문의 i가 column역할을 하게 된다.
10. 각 컬럼별로 row에 해당하는 값이 T인지, 즉 비트가 켜져있는지 체크하여 cnt + 1을 해준다.
11. 각 컬럼에 대한 cnt 계산이 끝났을때, 해당 열을 뒤집던지 뒤집지 않던지 둘 중 하나를 선택하는 것으로 해당 열의 최적해가 정해진다.
12. sum에 더해주고 나머지 행 계산을 진행한다.
13. 리턴값과 min 연산을 진행한다.
14. 나머지 재귀 호출 과정에서 구해진 sum을 가지고 최솟값을 계속 구한다.

import Foundation
var n: Int = 0
var a = [Int](repeating: 0, count: 44)
var ret = Int.max

func go(_ here: Int) {
    if here == n + 1 {
        var sum = 0
        var i = 1
        while i <= (1 << (n - 1)) {
            var cnt = 0
            for j in 1...n {
                if a[j] & i != 0 {
                    cnt += 1
                }
            }
            sum += min(cnt, n - cnt)
            i *= 2
        }
        ret = min(ret, sum)
        return
    }
    go(here + 1)
    a[here] = ~a[here]
    go(here + 1)
}

if let input = readLine() {
    n = Int(input) ?? 0
}

for i in 1...n {
    if let s = readLine() {
        var value = 1
        for char in s {
            if char == "T" {
                a[i] |= value
            }
            value *= 2
        }
    }
}

go(1)
print(ret)