[백준] 1074번 Z 파이썬

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

1074번: Z

import sys

N, R, C = map(int, input().split())
cnt = 0

def do_job(r, c, n):
    global cnt
    if not (r <= R < r + n and c <= C < c + n):
        cnt += n * n
        return
    if n == 2:
        for i in range(2):
            for j in range(2):
                if r + i == R and c + j == C:
                    print(cnt)
                    sys.exit()
                cnt += 1
        return
    for k in range(2):
        for l in range(2):
            do_job(r + n // 2 * k, c + n // 2 * l, n // 2)


do_job(0, 0, 2 ** N)

 

[시간초과]

처음에는 처음부터 끝까지 하나하나 카운트를 했더니 시간초과가 발생하였다.

하지만 생각해보면 분할영역내에 찾고자하는 행열번호의 칸이 존재하지 않으면 

해당 분할영역 칸마다 포문돌며 카운트를 할게 아니라 분할영역의 칸 개수 만큼 카운트를 더하고 다음영역으로 넘어가면 된다.

if not (r <= R < r + n and c <= C < c + n):
    cnt += n * n
    return