[알고리즘] 백준 - 1074

[Gold V] Z - 1074

문제 링크

성능 요약

메모리: 21344 KB, 시간: 116 ms

분류

분할 정복, 재귀

제출 일자

2025년 4월 6일 19:11:19

문제 설명

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2² × 2² 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

package baekjoon.april2025

fun main() {
    val (n, r, c) = readln().split(" ").map { it.toInt() }

    fun recur(n: Int, r: Int, c: Int): Int {
        if (n == 0) return 0

        val half = (1 shl (n - 1))

        // 1번째 칸일 때
        if (r < half && c < half) return recur(n-1, r, c)
        // 2번째 칸일 때
        if (r < half && c >= half) return recur(n-1, r, c - half) + (half * half)
        // 3번째 칸일 때
        if (r >= half && c < half) return recur(n-1, r - half, c) + (2 * half * half)
        // 4 번째 칸일 때
        return recur(n-1, r - half, c - half) + (3 * half * half)
    }

    println(recur(n, r, c))
}