문제

문제 링크 : https://www.acmicpc.net/problem/1074

풀이

분할 정복과 재귀를 사용해서 푸는 문제이다.

1. 우선 사각형을 4조각으로 자른다.
2. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서(z자)로 돌면서 r행 c열이 4개의 사각형 중 어느 사각형에 속하는지 확인한다.
3. 만약 4개의 사각형 중 k번째 사각형에 r행 c열이 속한다면 k-1번째까지의 사각형에 있는 길이가 1인 사각형의 개수를 계산해서 변수 cnt에 더해준다.
4. 자른 사각형의 변의 길이가 1이 될 때까지 1~3의 과정을 반복해준다.

배열의 크기가 2^15 x 2^15까지 커질 수 있기 때문에 모든 경우를 탐색하면 시간 초과가 뜬다. 따라서 사각형을 4개로 쪼갠 뒤에 r행 c열이 존재하는 사각형 외의 나머지 3개의 사각형은 재귀를 통해 탐색을 진행하면 안 된다.

from sys import stdin

n, r, c = map(int,stdin.readline().split())

cnt = 0
result = -1

def divAndCon(x,y,length):
    global r, c, result, cnt
    if length == 1:
        result = cnt
    else:
        parameter = [(x,y,length // 2), (x, y + length // 2, length // 2), (x + length // 2, y, length // 2), (x + length // 2, y + length // 2, length // 2)]
        ordCount = -1        
        for i in parameter:
            nx, ny, nl = i
            ordCount += 1
            if nx <= r < nx + nl and ny <= c < ny + nl:
                cnt += (nl ** 2) * ordCount
                divAndCon(nx,ny,nl)

divAndCon(0,0,2 ** n)
print(result)