[swift] 백준 - 1074번: Z

1074번: Z

---

나의 풀이

let inputs = readLine()!.split(separator: " ").map{Int(String($0))!}
var (n, r, c) = (inputs[0], inputs[1], inputs[2])
func solution(_ n: Int, _ r: Int, _ c: Int) -> Int {
    guard n > 0 else { return 0 }
    return 2 * (r % 2) + (c % 2) + 4 * solution(n - 1, r / 2, c / 2)
}
print(solution(n, r, c))

풀이 키워드

분할탐색
재귀함수
해당 문제는 위치정보를 가지고 해당 위치가 4분면 중 어디에 위치하는지 파악하여
재귀 마다 2차원 배열의 제곱만큼 4를 곱해주고 위치를 절반씩 나눠 빠르게 답을 찾을 수 있다.

예시)
입력
n: 3, r: 7, c: 7

solution함수의 재귀 형태(스택)

0
2 * (1 % 2) + (1 % 2) + 4 * solution(n - 1, r / 2, c / 2)	2 * 1 + 1 + 4 * 0 = 3
2 * (3 % 2) + (3 % 2) + 4 * solution(n - 1, r / 2, c / 2)	2 * 1 + 1 + 4 * 3 = 15
2 * (7 % 2) + (7 % 2) + 4 * solution(n - 1, r / 2, c / 2)	2 * 1 + 1 + 4 * 15 = 63

return: 63

---