[Kotlin, S2] 백준 1780번 종이의 개수

출처: unsplash.com

 

종이의 개수(1780번)

Silver 2

#분할 정복 #재귀

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

 

문제 내용

 

 

문제 접근

종이가 -1 또는 0 또는 1로 모두 채워지지 않았을 때, 정확히 9등분을 해 다시 종이가 -1 또는 0 또는 1인지 확인해서

-1, 0, 1로 채워진 종이의 개수를 세서 출력하면 된다.

 

시작 좌표와 확인할 size를 정한 다음, 시작 좌표에서 size만큼의 범위를 확인해 숫자의 개수를 세주는 방식의 재귀 호출을 통해 해결할 수 있다.

 

 

문제 해결 코드

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

private var paper = arrayOf(arrayOf<Int>())
private var cntMinus1 = 0
private var cnt0 = 0
private var cnt1 = 0

fun main() {
    val bf = BufferedReader(InputStreamReader(System.`in`))
    val n = bf.readLine().toInt()
    paper = Array(n + 1) { Array(n + 1) { 0 } }

    for (i in 1 .. n) {
        val line = bf.readLine().split(" ").map { it.toInt() }

        for (j in 1 .. n) {
            paper[i][j] = line[j - 1]
        }
    }

    cutting(1, 1, n)

    println("$cntMinus1 $cnt0 $cnt1")
}

private fun cutting(x: Int, y: Int, size: Int) {
    val check = paper[y][x]
    var cnt = 0
    for (i in y until y + size) {
        for (j in x until x + size) {
            if (paper[i][j] == check) cnt++
        }
    }

    if (cnt == size * size) {
        when (check) {
            0 -> cnt0++
            1 -> cnt1++
            -1 -> cntMinus1++
        }
    } else {
        for (cy in y until  y + size step size / 3) {
            for (cx in x until x + size step size / 3) {
                cutting(cx, cy, size / 3)
            }
        }
    }
}

 

문제 풀이

입력값을 저장할 paper와 -1, 0, 1 종이의 개수를 세줄 변수를 생성한다.

 

check로 개수를 세줄 숫자를 정하고

시작 좌표에서 size만큼의 범위를 순회하면서 check과 동일한 값의 개수를 세준다.

 

cnt가 size * size와 같다면 확인하는 면이 모두 check와 동일하다는 뜻이 된다.

입력값이 항상 정사각형이고 길이도 3의 제곱수만으로만 주어지기 때문에 가능하다.

 

cnt가 size * size와 다르면 현재범위에서 9등분을 해야 하기 때문에 step size / 3을 이용해 9개의 시작 좌표를 모두 구할 수 있다.

구한 시작 좌표와 size / 3으로 범위를 좁혀 함수를 다시 호출하면 된다.

 

 

문제 해결 과정

푸는데 큰 어려움은 없었다.

재귀 호출을 어떻게 할지 설계만 잘하면 된다.

 

체감 난이도 Silver 3 ~ Silver 2