[알고리즘 문제풀이] Z

문제 제목 : Z

문제 난이도 : 중

문제 유형 : 재귀함수

https://www.acmicpc.net/problem/1074
시간 제한 : 0.5초
메모리 제한 : 512MB

문제풀이 아이디어

< 소스코드 >

import sys

def z(n, r, c):
    global result
    # 찾는 좌표라면 result를 출력하고 종료
    if r == R and c == C:
        print(int(result))
        exit(0)
       
    if n == 1:
        result += 1
        return

    # 탐색 증인 배열 중에 찾는 좌표가 없다면 좌표에 크기를 더한다.
    # 예를 들어 3사분면에 있다면 1, 2사분면은 검사할 필요 x -> 스킵
    if not (r <= R < r + n and c <= C < c + n):
        result += n * n
        return

    # 1/2/3/4사분면을 재귀적으로 탐색
    z(n/2, r, c) # 1사분면
    z(n/2, r, c + n/2) # 2사분면
    z(n/2, r + n/2, c) # 3사분면
    z(n/2, r + n/2, c + n/2) # 4사분면


N, R, C = map(int, sys.stdin.readline().split())
result = 0

# 2^n을 0, 0부터 탐색
z(2 ** N, 0, 0)