Today I Learned
오늘은 백준에서 코틀린으로 코테문제를 풀었다.
Z
https://www.acmicpc.net/problem/1074
문제
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
풀이과정
- 그림을 보면
Z패턴이 z 모양처럼 반복되는 것을 알 수 있다. 그래서 가로를 절반, 세로를 절반으로 나누면 크게 4사분면이 되는데 이 반복 패턴을 재귀로 구현해서 문제를 풀었다.
-
입력을 readln().split(" ").map { it.toInt() } 코드로 바로 3개의 변수에 받아 준다.
-
recur() 함수로 재귀 함수를 만든다.
-
4사분면에서 한 변의 크기는
shl함수로 구해준다. 한 변은 2의 n-1승이므로 1 shl (n-1)로 구한다. 여기서 1은 2의 1승 즉 2를 의미한다.
- shl 함수
shift left 즉, 이진 표현에서 비트를 왼쪽으로 이동한다.
val shl shiftAmount 에서
val을 shiftAmount 만큼 왼쪽으로 비트를 옮긴다는 뜻이다.
-
주어진 r, c 변수의 숫자에 따라 when으로 0,1,2,3중 몇 사분면에 해당하는지 찾는다.
-
각 사분면은 이전 사분면 크기의 제곱만큼 크다. 즉, 해당 사분면의 오프셋은 이전 사분면의 크기의 제곱에 현재 사분면의 번호를 곱한 것이다. 이를 이용해 오프셋을 구한다.
-
return에 오프셋만큼 계속 더해주고, 재귀로 recur()함수를 n은 하나 줄이고, r과 c는 halfSize를 차감한 만큼 리턴하면 완료.
Kotlin 코드
fun main() {
val (n, r, c) = readln().split(" ").map { it.toInt() }
print(recur(n,r,c))
}
fun recur(n: Int, r: Int, c: Int): Int {
if (n == 0) return 0
val halfSize = 1 shl (n - 1)
val quadrant = when {
r < halfSize && c < halfSize -> 0
r < halfSize && c >= halfSize -> 1
r >= halfSize && c < halfSize -> 2
else -> 3
}
val offset = halfSize * halfSize * quadrant
return offset + recur(n - 1, r % halfSize, c % halfSize)
}