[백준 1285] - 동전 뒤집기(Kotlin)[골드1]

문제

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

1285번: 동전 뒤집기

 

문제 풀이

동전에 대해 행과 열을 뒤집는 순서가 중요한 문제라고 생각했다.

우리가 선택할 수 있는 경우의 수는 뒤집느냐, 뒤집지 않느냐이다.

하지만 n의 최대 크기가 20이기에 최대 행에 대해 2^20, 열에 대해 2^20이 발생하기 때문에 최적화가 필요했다.

작업의 순서가 중요한 점과 브루트포스로 n을 돌릴 경우 시간초과가 당연한 사실에서 저번에 풀었던 외판원 문제가 떠올랐다.

외판원 문제도 도시를 방문하느냐, 안 하느냐에 대한 2가지 경우의 수가 존재하고, 해당 문제도 동전을 선택하느냐, 하지 않느냐에 대한 2가지 경우의 수가 존재하기 때문에 비슷하게 풀면 될 것이라고 생각했다.

 

자 그렇다면 비트마스킹을 어떻게 이용할까?

통상적으로 방문에 대한 정보를 따로 배열을 만들어서 기록하는것이 메모리적으로 손해이기 때문에 비트마스킹을 통해서 방문 정보를 저장하는 풀이가 보통적이다.

 

따라서 나는 행을 뒤집는 정보를 비트마스킹으로 저장하고, 열을 뒤집는 정보를 비트마스킹으로 저장했다.

for(i in 0 until n){
	val next = 1 shl i
    if(rowVisited and next==0){
    	//동전을 뒤집다는 정보를 저장하고 재귀 호출
        function(rowVisited or next , colVisited)
    }
    function(rowVisited, colVisited) //행 동전 뒤집지 않기
    if(colVisited and next == 0){
    	function(rowVisited,colVisited or next)
    }
    function(rowVisited,colVisited)
}

 

이렇게 하니 재귀 호출이 무려 4번이 일어났다..

비트마스킹을 통해서 최적화를 한 목적은 방문 정보를 저장하기 위함이지, 연산의 수를 줄여주지 않는다.

따라서 연산의 수를 줄여야 했다.

 

우리는 동전을 뒤집어서 앞면을 최소로 해야 한다.

내 풀이에 연산이 많은 것은 행과 열을 동시에 신경썼기 때문이다.

1번 행을 뒤집기 ->  2번행 뒤집기 -> 1번 열을 뒤집기 Vs 1번 행 뒤집기 -> 1번 열 뒤집기 -> 2번 행 뒤집기를 비교해 보자.

각 순서마다의 동전의 앞면 수는 다르지만, 최종적으로 같은 모양을 그리는 것을 알 수 있다.

당연하게도 각 동전에 대해 뒤집는 수가 같기 때문이다.

 

그렇기 때문에 행에 대해서 모든 경우의 수로 뒤집어 보고, 열에 대해서 검사해 보는 것이다.

열에 대해서 검사를 할 때는 열의 앞면 동전의 수를 기준으로 절반보다 많다면 뒤집는 것이 결과에 유리할 것이다.

왜냐하면 우리는 최소의 동전을 앞면으로 만들어야 하기 때문이다.

 

이렇게 행을 뒤집는 정보를 먼저 계산하고, 열을 뒤집는 경우에 대해서 검사해 보면 문제는 해결된다.

전체 코드

import kotlin.math.*

class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0
    private lateinit var graph: Array<BooleanArray>
    private var frontCoin = Int.MAX_VALUE
    fun run() {
        input()
        solve()
        print(frontCoin)
    }

    private fun input() {
        n = br.readLine().toInt()
        graph = Array(n) { BooleanArray(n) }
        for (i in 0 until n) {
            val line = br.readLine()
            for (j in 0 until n) {
                if (line[j] == 'H') {
                    graph[i][j] = false
                } else {
                    graph[i][j] = true
                }
            }
        }
    }

    private fun solve() {
        flipCoin(0, 0)
    }

    private fun flipCoin(now: Int, rowVisited: Int) {
        if (now == n) {
            frontCoin = min(frontCoin, checkFrontCoin(rowVisited))
            return
        }
        val next = 1 shl now
        flipCoin(now + 1, rowVisited or next)
        flipCoin(now + 1, rowVisited)
    }

    private fun checkFrontCoin(rowVisited: Int): Int {
        var sum = 0
        for (j in 0 until n) {
            var front = 0
            for (k in 0 until n) {
                val next = 1 shl k
                if (rowVisited and next != 0) { //뒤집어야 행인 경우
                    if (!graph[k][j]) {
                        front += 1
                    }
                    continue
                }
                if (graph[k][j]) {
                    front += 1
                }
            }
            sum += min(front, n - front)
        }
        return sum
    }
}

fun main() {
    Solution().run()
}