[백준/BOJ] 1455번: 뒤집기 II

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

1455번: 뒤집기 II

문제

세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다.

동전의 앞면을 0이라고 하고 뒷면을 1이라고 했을 때, 세준이는 모든 동전을 뒤집어서 앞면으로 만들려고 한다.

세준이가 (a,b)칸을 뒤집으려고 한다면, (i,j) (1 ≤ i ≤ a, 1 ≤ j ≤ b)의 조건을 만족하는 a×b개의 동전이 한번에 모두 뒤집힌다. (i는 위에서부터 위치의 위치이고, j는 왼쪽에서 부터의 위치이다.)

세준이가 뒤집어야하는 동전의 개수를 출력하시오. (a,b)칸을 선택해서 a×b개가 뒤집혔다면, 동전을 뒤집은 횟수는 a×b가 아니라 1이다.

해설

(a, b) 칸이 1(뒷면)이라면 (0, 0)부터 (a, b)까지를 뒤집는다.

따라서 맨 뒤에서부터 반복을 하며 특정 동전이 뒷면일 때 (0, 0)부터 그 위치까지 전부 뒤집으면 된다.

 

맨 앞까지 반복을 끝냈다면 동전에 1은 남아있지 않을 것이므로

뒤집은 횟수를 세어주면 된다.

소스 코드

lateinit var coin: Array<IntArray>

fun main() = with(System.`in`.bufferedReader()) {
    val (n, m) = readLine().split(" ").map {it.toInt() }
    coin = Array(n) { IntArray(m) { 0 } }
    for(i in 0 until n) {
        val input = readLine()
        for(j in 0 until m) {
            coin[i][j] = (input[j] - 48).toInt()
        }
    }
    var cnt = 0
    for(i in n - 1 downTo 0){
        for(j in m - 1 downTo 0) {
            if(coin[i][j] == 1) {
                cnt++
                reverse(i, j)
            }
        }
    }
    println(cnt)
}

fun reverse(y: Int, x: Int) {
    for(i in 0 .. y) {
        for(j in 0 .. x) {
            coin[i][j] = 1 - coin[i][j]
        }
    }
}