[BOJ] Z

---

코드

import sys
input = sys.stdin.readline

N, r, c = map(int, input().split())

ans = 0

while N != 0:
    N -= 1

    # 1사분면 (0)
    if r < 2**N and c < 2**N: 
        ans += 0    # (2**N) * (2**N) * 0

    # 2사분면 (1)
    if r < 2**N and c >= 2**N:
        ans += (2**N) * (2**N) * 1
        c -= (2**N)

    # 3사분면 (2)
    if r >= 2**N and c < 2**N:
        ans += (2**N) * (2**N) * 2
        r -= (2**N)

    # 4사분면 (3)
    if r >= 2**N and c >= 2**N:
        ans += (2**N) * (2**N) * 3
        r -= (2**N)
        c -= (2**N)

print(ans)

결과

풀이 방법

• 규칙성을 찾고 분할정복을 활용하는 문제였다.
• 2^N * 2^N 좌표를 4개 구역으로 반복적으로 나누면서 답에 도달한다.
• 현재 구역에서 좌표 (r,c)가 몇 사분면에 있는지 확인한 다음, 각 사분면에 따라 (r,c), ans 값을 수정한다.
• 1사분면에 있는 경우 해당 사분면에서 다음 반복을 실행하므로 그 전에 좌표값을 수정할 필요가 없다. ans는 (2^N) x (2^N) x 0 만큼 더한다.
• 2사분면에 있는 경우 다음 반복 실행 전에 c 좌표를 2^N만큼 빼주고, 2사분면의 (0,0)에 해당하는 값 2^N x 2^N x 1를 ans에 더한다.
• 3사분면에 있는 경우 다음 반복 실행 전에 r 좌표를 2^N만큼 빼주고, 3사분면의 (0,0)에 해당하는 값 2^N x 2^N x 2를 ans에 더한다.
• 4사분면에 있는 경우 다음 반복 실행 전에 r, c 좌표를 2^N만큼 빼주고, 4사분면의 (0,0)에 해당하는 값 2^N x 2^N x 3를 ans에 더한다.

---