1074번: Z

문제 출처 : https://www.acmicpc.net/problem/1074

 

언어 : Kotlin

 

문제 설명 :

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

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

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

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

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

• 첫째 줄에 정수 N, r, c가 주어진다.
• r행 c열을 몇 번째로 방문했는지 출력한다.

 

제한 사항 :

• 시간 제한 : 0.5초 (추가 시간 없음)
• 메모리 제한 : 512MB
• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

 

입출력 예 :

입력	출력
2 3 1	11
3 7 7	63
1 0 0	0
4 7 7	63
10 511 511	262143
10 512 512	786432

다른 사람의 풀이 : 

import java.io.*

var answer = 0
var numbering = 0

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val (n, r, c) = br.readLine().split(" ").map { it.toInt() }
    cal(1 shl(n), 0, 0, r, c)

    bw.write("$answer")
    bw.flush()
    bw.close()
}

fun cal(size: Int, row: Int, col: Int, targetRow: Int, targetCol: Int) {
    if (targetRow !in row until row + size || targetCol !in col until col + size) {
        numbering += size * size
        return
    }

    if (row == targetRow && col == targetCol) {
        answer = numbering
        return
    }

    val halfSize = size / 2

    cal(halfSize, row, col, targetRow, targetCol)
    cal(halfSize, row, col + halfSize, targetRow, targetCol)
    cal(halfSize, row + halfSize, col, targetRow, targetCol)
    cal(halfSize, row + halfSize, col + halfSize, targetRow, targetCol)
}

 

갈수록 문제가 죄다 어려워지는 것 같다.

 

https://best-human-developer.tistory.com/48

백준 1074번: Z (Kotlin)