Z

1074번: Z

 

나의 풀이 : (분할 정복.. 아이디어 생각하는게 너무 어려웠습니다.. ㅠㅠ)

import sys
# n : 맵 크기, (r,c) : 좌표
N, r, c = map(int, sys.stdin.readline().rstrip().split())

def div_map(N, r, c):
    if N == 0:
        return 0

    half = 2**(N-1)
    map_size = half * half
    
    # 1사분면
    if (r < half) and (c < half):
        return div_map(N-1, r, c)
    # 2사분면
    if (r < half) and (c >= half):
        return map_size + div_map(N-1, r, c-half)
    # 3사분면
    if (r >= half) and (c < half):
        return map_size * 2 + div_map(N-1, r-half, c)
    # 4사분면
    else:
        return map_size * 3 + div_map(N-1, r-half, c-half)

print(div_map(N, r, c))

 

시간 복잡도

def div_map(N, r, c) : 조건 만족시 까지 분할정복하는 함수 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도는 : 선형 시간 복잡도 ( O(n) )