[Algorithm] 백준 - 1074번 Z (Swift)

문제 소개

월요일을 기념하며... 약간은 풀만한 문제(?)에 도전했다..! 문제에 친절하게도 재귀적으로 방문한다는 힌트가 있다! 🥸

문제 풀이

재귀적으로 어떻게 구할 수 있을까? 고민해봤다. 아래와 같은 형태가 반복되지 않을까? 함수로 치면 어느 사분면에 있는지 판단 한 후 그것을 계속 잘게 잘게 쪼개서 구하는 방식으로 재귀적으로 구하면 될 것 같았다.

그림으로 이해가 될지는 모르겠지만... (x, y)를 구했다면 x의 경우 (블록 * 2), y의 경우 (블록 * 1)을 곱해줘서 몇번째 순서인지 계속 쌓아나가면 된다!

import Foundation

let nrc = readLine()!.components(separatedBy: " ").map { Int($0)! }
let (n, r, c) = (nrc[0], nrc[1], nrc[2])

var ans = 0

func analyze(n: Int, r: Int, c: Int) {
    let div = 1 << n
    let block = div * div
    ans += r / div * block * 2 + c / div * block * 1
    if n > 0 { analyze(n: n - 1, r: r % div, c: c % div) }
}

analyze(n: n-1, r: r, c: c)
print(ans)