[백준] 1074 (Z)

#1 알고리즘

N = 2 이상인 큰 문제를, N = 1이 될 때까지 작은 문제로 쪼개어 푼다. 그러려면 f(큰 문제) = 작은 문제인 f(x)를 알아야 한다. 규칙을 수식으로 표현해내어야 한다. '바둑판'의 영역을 4개로 나누어보자. 그리고 각 영역의 맨 ↖에 있는, 영역의 첫 원소들을 비교한다.

 

영역 m ~ 영역 (m + 1) 간 첫 원소의 값 차이는 N = 1일 때 1, N = 2일 때 4, N = 3일 때 16, N = 4일 때 64 ... 다. 이를 일반화하면 영역 간 첫 원소의 값 차이(interAreaFirstElementDifference)는 2^(N-1)*2이다.

 

즉 어떤 영역 m에 있어, 칸마다 써진 수는 (영역 0의 수) + m * 2^(N-1)*2다. 보라색 글씨 부분을 축적된(accumulated) 값이라고 부르기로 한다.

 

이제 f(큰 문제) = 작은 문제인 f(x)를 도출할 수 있다. 이 때, 큰 문제에서의 r행 c열은 작은 문제에서의 r행 c열과 항상 같지 않으므로, f(x)에 r값과 c값을 적절히 조절하는 로직도 추가한다. '바둑판'의 한 변의 길이는 2^N이므로, 그 절반인 2^N / 2 = 2^N-1만큼(sideLengthHalf) r값이나 c값을 적절히 조정하면 된다.

 

#2 코드 - 코틀린

import kotlin.math.pow

/*

area 0 | area 1
---------------
area 2 | area 3

*/

fun main() {
    val input = readln().split(" ")
    val n = input[0].toInt()
    val r = input[1].toInt() // rowIndex
    val c = input[2].toInt() // columnIndex

    println(calculateVisitIndex(n, r, c, 0))
}

fun calculateVisitIndex(nArgs: Int, rArgs: Int, cArgs: Int, accumulatedArgs: Int): Int {
    if (nArgs == 1) {
        return accumulatedArgs + (rArgs * 2) + cArgs
    }

    var r = rArgs
    var c = cArgs
    var accumulated = accumulatedArgs

    val interAreaFirstElementDifference = exponentiation(2, (nArgs - 1) * 2)
    val sideLengthHalf = exponentiation(2, nArgs - 1)

    when (calculateTargetArea(nArgs, rArgs, cArgs)) {
        0 -> { // 아무것도 안 함
        }

        1 -> {
            c -= sideLengthHalf
            accumulated += interAreaFirstElementDifference * 1
        }

        2 -> {
            r -= sideLengthHalf
            accumulated += interAreaFirstElementDifference * 2
        }

        3 -> {
            r -= sideLengthHalf
            c -= sideLengthHalf
            accumulated += interAreaFirstElementDifference * 3
        }
    }

    return calculateVisitIndex(nArgs - 1, r, c, accumulated)
}

fun exponentiation(base: Int, exponent: Int): Int { // 거듭제곱
    return base.toDouble().pow(exponent.toDouble()).toInt()
}

fun calculateTargetArea(n: Int, r: Int, c: Int): Int {
    if (r < exponentiation(2, n - 1)) {
        if (c < exponentiation(2, n - 1)) { // area 0
            return 0

        } else { // area 1
            return 1
        }

    } else {
        if (c < exponentiation(2, n - 1)) { // area 2
            return 2

        } else { // area 3
            return 3
        }
    }
}