1018번: 체스판 다시 칠하기

문제 출처 : https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

언어 : Kotlin

 

문제 설명 :

지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

 

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

 

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

• 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
• 첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
8 8 WBWBWBWB BWBWBWBW WBWBWBWB BWBBBWBW WBWBWBWB BWBWBWBW WBWBWBWB BWBWBWBW	1
10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB	12
더 많은 입출력 예제

다른 사람의 풀이 : 

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, m) = br.readLine().split(" ").map { it.toInt() }
    val arr = Array(n) { Array(m) { 0 } }
    var min = n * m

    for (i in 0 until n) {
        val line = br.readLine().chunked(1)

        for (j in 0 until m) {
            if (((i + j) % 2 == 0 && line[j] != "W") || ((i + j) % 2 != 0 && line[j] != "B")) arr[i][j]++
            if (j > 0) arr[i][j] += arr[i][j - 1]
        }
    }

    for (i in 0 .. n - 8) {
        for (j in 0 .. m - 8) {
            var cnt = 0

            for (k in i until i + 8) {
                cnt += arr[k][j + 7]

                if (j > 0) cnt -= arr[k][j - 1]
            }

            if (cnt > 64 - cnt) cnt = 64 - cnt
            if (cnt < min) min = cnt
        }
    }

    bw.write("$min")
    bw.flush()
    bw.close()
}

https://jionchu.tistory.com/99

[백준/Kotlin] 1018번: 체스판 다시 칠하기

 

 

내가 시도하다 포기한 풀이는 다음과 같다.

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, m) = br.readLine().split(" ").map { it.toInt() }
    val temp = Array(n) { Array(m) { 0 } }
    for (i in 0 until n) {
        val line = br.readLine().chunked(1)

        for (j in 0 until m) {
            if (line[j] == "B") {
                temp[i][j] = 1
            } else {
                temp[i][j] = -1
            }
        }
    }

    var checker = emptyArray<Int>()

    for (i in 0 .. n - 8) {
        for (j in 0 .. m - 8) {
            var cnt = 0

            val newTemp = temp.map { it.sliceArray(j .. j + 7) }.slice(i .. i + 7)
            checker += newTemp.sumOf { it.sum() }
            println("$i, $j | ${newTemp.map { it.sum() }.filter { it == 4 }}")
        }
    }

    println("min | ${checker.min()}")
    bw.flush()
    bw.close()
}

해당 라인의 총합을 통해 구하고자 하니 BWBWBW or WBWBWB 이 두가지로 나뉘어 시작했을 때

중간에 순서가 틀리는 경우를 구별할 수 없어서 실패했다.