[백준] 1074번 : Z - Python(파이썬)

문제

https://www.acmicpc.net/problem/1074

1074번: Z

아이디어

1.  사분면 나누는 기준점 설정

한 변 2^N을 절반인 2로 나누기  

2^N / 2  =  2^(N-1)

2. 본인 좌표 도달한 경우

더 이상 이전에 방문한 사분면이 없기 때문에 0을 반환하며 총 방문값에 더해 끝냄

3. 한 사분면에 대한 개수 * 지나온 사분면 갯수

(한 변) * (한 변) = 한 사분면 갯수

좌표가 해당하는 사분면 - 1 = 지나 온 사분면 갯수

 

전체코드

#https://www.acmicpc.net/problem/1074


import sys
input=sys.stdin.readline

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

# return : 0, 1, 2, 3 (몇 사분면에 해당하는지 반환)
def quad(n, r, c):

    num = 2**(n-1)

    # 해당 함수는 몇사분면 위인지 확인?
    if (r < num) & (c < num): # 1사분면
        return 0
    elif (r < num) & (c >= num): # 2사분면
        return 1
    elif (r >= num) & (c < num): # 3사분면
        return 2
    else: # 4사분면
        return 3

def visit(n,r,c):
    if n==1:
        return quad(n,r,c)
    q=quad(n,r,c)
    size=2**(n-1)
    visited=size*size*q
    if q==0:
        return visited+visit(n-1,r,c)
    elif q==1:
        return visited + visit(n-1,r,c-size)
    elif q==2:
        return visited + visit(n-1, r-size,c)
    else:
        return visited + visit(n-1, r-size,c-size)
        
print(visit(n, r, c))