1074 Z

Today 1/16

Z (My Code)

func Zcircuit(_ N: Int, _ r: Int, _ c: Int) {
    if N == 0 { return }
    let divide = Int(pow(2,Double(N))) / 2
    if r < divide && c < divide {
        count += 0
        Zcircuit(N-1, r, c)
    } else if r < divide && c >= divide {
        count += Int(pow(4,Double(N-1))) * 1
        Zcircuit(N-1, r, c-divide)
    } else if r >= divide && c < divide {
        count += Int(pow(4,Double(N-1))) * 2
        Zcircuit(N-1, r-divide, c)
    } else {
        count += Int(pow(4,Double(N-1))) * 3
        Zcircuit(N-1, r-divide, c-divide)
    }
}

let Nrc = readLine()!.split(separator: " ").map{Int(String($0))!}
let (N, r, c) = (Nrc[0], Nrc[1], Nrc[2])
var count = 0
Zcircuit(N, r, c)
print(count)

어떤 유형인지 파악이 오래 걸렸다. 계속 생각하다가, 이것도 재귀함수로 풀 수 있지 않을까 하는 생각이 들었다.

그러고 4사분면으로 나눠서 각 사분면의 시작 숫자의 규칙이 있나 살펴보았다. 각 사분면은 4^N-1 * (사분면의 숫자-1)로 시작하는 규칙을 발견할 수 있었다. 이를 이용해서 재귀함수를 만들어서 쉽게 풀 수 있었다.

• 성공하고나서 다른 사람들은 어떻게 풀었나 살펴보니 보통은 나처럼 시작 숫자로 하는게 아니라 사분면별로 나눠서 큰 조각들의 숫자를 계속 더해가는 방식으로 푼 것 같았다. (근데 사실 개념적으로는 똑같은 것 같다)
• 재귀함수,, 정도로만 생각하고 풀었는데 분할 정복이라는 멋있는 명칭이 있었다. 생각이 나는 것 같기도 하다.