[백준][코틀린][1285] 동전 뒤집기

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

1285번: 동전 뒤집기

문제 풀이

1. 주어진 동전들에 대해서 행/열을 각각 회전할 수 있다. 이때 행을 기준으로만 볼때 N=3 일 경우 다음과 같은 경우의 수로 행을 회전할 수 있다.

- 행의 회전 경우의 수

    1) 행을 회전하지 않는 경우 : 1가지

    2) 하나의 행을 회전하는 경우  : (0행, 1행, 2행) : 3가지

    3) 두 개의 행을 회전하는 경우 : (0, 1), (0, 2), (1, 2) : 3가지

    4) 세 개의 행을 회전하는 경우 : (0, 1, 2) : 1가지

2. 위의 경우 수는 총 8가지로 2^N 가지의 경우의 수를 가진다.

3. 2번에서 구한 행을 회전하는 경우의 수에 해서 각 열을 회전하거나 회전하지 않았을 때 각각 뒷면의 동전 개수 중 최소 값을 구한다.

즉 아래의 그림과 같이 행의 경우의 수에 대해서 각 열에 대한 뒷면의 개수를 구한다.

4. 뒷면의 개수의 최소 값을 result 에 저장한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val coin = Array(N) { BooleanArray(N) { false } }

    repeat(N) { index1 ->
        br.readLine().map { it }.forEachIndexed { index2, c ->
            // 뒷면이면 true, 앞면이면 false 로 저장한다.
            coin[index1][index2] = c == 'T'
        }
    }

    var result = Int.MAX_VALUE

    //기준을 행으로 잡고 행을 뒤집는 모든 경우의 수(2^N) 를 구한다.
    //이때 bitmask 를 이용해서 모든 경우의 수(부분집합)를 구하면 시간이 단축된다.
    for (i in 0 until (1 shl N)) {
        var sum = 0

        for (col in 0 until N) {
            var back = 0
            for (j in 0 until N) {
                var current = coin[j][col]

                if (i and (1 shl j) != 0) {
                    current = !coin[j][col]
                }

                if (current) {
                    back++
                }
            }

            sum += Math.min(back, N - back)
        }

        result = Math.min(result, sum)
    }

    println(result)
}