[6개월 안에 백준 플래티넘 달성하기] 6. 색종이 만들기 2630 | 코틀린

색종이 만들기 문제는 정답비율이 69%로 쉽게 접근하였으나 풀지 못한 문제입니다.

이 문제의 경우 어떤 알고리즘 기법으로 접근하는지에 따라 문제의 난이도가 달라지는 거 같습니다.

 

저 같은 경우에는 구현 또는 BFS로 문제에 접근하였으나 여러 가지 예외 케이스가 발생하였고 이를 해결하지 못하여 풀지 못하였습니다.

해당 문제는 분할 정복 기법으로 풀 수 있으며 꽤 간단한 로직으로 답을 구할 수 있습니다.

 

문제

 

풀이

분할 정복이라는 말처럼 NxN의 색종이를 4등분으로 분할해 나가면서 조건에 맞는지 체크해 주면 됩니다.

분할하는 과정에서 재귀함수가 사용됩니다.

재귀 흐름

fun main() = with(System.`in`.bufferedReader()){
    val N = readLine().toInt()
    val arr = Array(N) { IntArray(N) }
    // 입력문 받는 코드
    repeat(N) { index ->
        val line = readLine().split(" ").map {it.toInt()}
        for (i in line.indices) {
            arr[index][i] = line[i]
        }
    }
    
    var w_count = 0  // 흰색 색종이 수
    var b_count = 0  // 파란색 색종이 수
    
    // 재귀 함수
    fun div_map(x: Int, y: Int, n: Int) {

        // 현재 범위를 돌면서 파란색 색종이 수 체크
        var tmp = 0
        for (i in x until x+n) {
            for (j in y until y+n) {
                if (arr[i][j] == 1) {
                    tmp++
                }
            }
        }
        
        // 파란색 색종이가 0일 경우 = 전부 흰색 색종이일 경우
        if (tmp == 0) { 
            w_count++
        } else if (tmp == n*n) { // 전부 파란색 색종이일 경우 
            b_count++
        } else {
            // 둘 다 아닌 경우 4등분으로 분할
            // 좌표는 각 4등분된 부분의 시작 지점으로 설정
            div_map(x, y, n/2)
            div_map(x+n/2, y, n/2)
            div_map(x, y+n/2, n/2)
            div_map(x+n/2, y+n/2, n/2)
        }
    }
    div_map(0,0,N)
    println(w_count)
    println(b_count)
}

 

 

답을 보면 생각보다 간단하고 충분히 풀 수 있었을 거 같다는 생각이 듭니다.

앞으로는 좀 더 문제에 대해 신중히 생각해 보고 풀이를 볼지 말지 결정해야 될 거 같습니다.