[백준-1074] Z ✨

❓ Problem

🤔 How

문제이름이 정말 직관적이라고 생각되는 문제

1. 2n * 2n 의 형태의 board 가 주어지고 입력받은 r,c 번째 원소는 언제 방문 하는지 출력하는 문제이다.

수학의 사분면으로 접근하기

수학의 사분면의 기준으로 현재 접근하는 사각형의 한변의 길이가 얼마인지 알수 있다면 모든 칸을 방문하지 않더라도 답을 도출 할 수 있다.

처음 탐색은 (0,0) 부터 탐색한다.

            if y + l <= r and x + l <= c:  # 목표가 4사분면 일떄
                return search(y + l, x + l, l, current + 3 * l**2)
            elif y + l <= r:  # 목표가 3 사분면 일때
                return search(y + l, x, l, current + 2 * l**2)
            elif x + l <= c: # 목표가 1 사분면 일때 
                return search(y, x + l, l, current + l**2)
            else: # 목표가 2 사분면일때
                return search(y, x, l, current) # current 변화없이 사각형의 길이만 반으로 줄이고 탐색한다.             

❗ Solve

# Z
import sys

input = sys.stdin.readline


def solution():
    n, r, c = map(int, input().split())

    def search(y, x, l, current):
        if (y, x) == (r, c):
            return current
        else:
            l //= 2
            if y + l <= r and x + l <= c:  # 목표가 4사분 면 일떄
                return search(y + l, x + l, l, current + 3 * l**2)
            elif y + l <= r:  # 목표가 3 사분면일떄
                return search(y + l, x, l, current + 2 * l**2)
            elif x + l <= c:
                return search(y, x + l, l, current + l**2)
            else:
                return search(y, x, l, current)
        pass

    pass
    print(search(0, 0, 2**n, 0))