문제

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

풀이

• $2^N \times 2^N$ 크기의 Z배열
• N이 주어졌을 때, r행 c열을 몇 번째에 방문하는가

처음 문제를 봤을 때, 분할 정복하면 쉽게 되겠다‼️ 하고 시작했습니다.
4등분으로 쪼개고 쪼개고 쪼개고..
하려고 했으나 문제 조건에 1 ≤ N ≤ 15 즉, 배열을 선언하고 문제를 풀면 2$^{15} \times$ 2$^{15}$.. 너무 커져 에러가 발생할 것 같더군요.
그래서 다른 분들의 풀이를 보며 문제를 이해해봤습니다.(이해하기 상당히 힘들었읍니다..)

제 풀이로 한 번 설명해보겠읍니다.

Z 모양으로 행렬을 방문하므로 행렬을 4등분하여 접근
(1사분면, 2사분면, 3사분면, 4사분면)

크기가 $2^N \times 2^N$인 행렬이 주어졌을 때 4등분하게 되면
각 부분은 $2^{N-1} \times 2^{N-1}$ 크기가 됩니다.

예를 들어 N=2일 때,

행의 크기는 $2^2$, 4등분을 하게 되면 $2^1$ 즉, $2^{N-1}$이 됩니다.

여기서 (r,c)가 어느 사분면에 속하는지 찾고 해당 사분면까지의 누적 방문 순서를 더하며 탐색을 줄여나가면 됩니다.

mid = $2^{N-1}$

1사분면

r < mid and c < mid

2사분면

r < mid and c >= mid

3사분면

r >= mid and c < mid

4사분면

r >= mid and c >= mid

(r,c)를 구하려면 (r,c)가 포함된 사분면이 몇 번째로 방문되는지 알아야 하고 이미 지나온 사분면들의 방문해야 합니다.

N=2일 때 행렬을 탐색해봅시다.
Z 모양을 위해 4등분하여줍니다.

이때 각 사분면을 보면

• 1사분면: 0~3
• 2사분면: 4~7 -> 이전 사분면(1사분면) 크기인 4를 더함
• 3사분면: 8~11 -> 이전 사분면(1,2사분면) 크기인 8을 더함
• 4사분면: 12~15 -> 이전 사분면(1,2,3사분면) 크기인 12를 더함

각 사분면은 4개의 블록을 가지게 됩니다.

• 1사분면 추가 방문 순서 = 0
• 2사분면 추가 방문 순서 = 1 * 4 = 4
• 3사분면 추가 방문 순서 = 2 * 4 = 8
• 4사분면 추가 방문 순서 = 3 * 4 = 12

이걸 점화식으로 나타내게 되면,

• 1사분면 = 0
• 2사분면 = 1 * mid^2
• 3사분면 = 2 * mid^2
• 4사분면 = 3 * mid^2

위 조건들을 이용하여 함수를 재귀적으로 반복해서 N=0까지 줄여나가면 정답을 찾을 수 있습니다.

예제를 통해 이해해봅시다.

N = 2, r = 3, c = 1

N = 2, mid = 2($2^{N-1}$)
(3,1) = 3사분면 = 이전 사분면 방문 순서 = 2 $\times$ 4 = 8회
새로운 좌표 (r-mid, c) = (1,1)

N = 1, mid = 1
(1,1) = 1사분면
추가 방문 X
(8 + 0 = 8)

이제 2 $\times$ 2 행렬을 보면:

0 1
2 3

4등분하게 되면 (1,1)은 4사분면이므로 결과에 +3
8+3 = 11

코드를 작성해볼게요

def func(n,r,c):
	if n == 0:
    	return 0

n = 0이면 행렬이 없는 것이니 0 반환

각 사분면 조건에 따라 코드를 작성

	mid = 2 ** (n-1)
    
    # 1사분면
    if r < mid and c < mid:
    	return func(n-1, r, c)
        
    # 2사분면
    elif r < mid and c >= mid:
        return mid * mid + func(n-1, r, c-mid)

    # 3사분면
    elif r >= mid and c < mid:
        return 2 * mid * mid + func(n-1, r-mid, c)
	
    # 4사분면
    else:
        return 3 * mid * mid + func(n-1, r-mid, c-mid)

굉장히 힘들었지면 어찌저찌 해결..🥲

코드

import sys
input = sys.stdin.readline

def func(n,r,c):   
    if n == 0:
        return 0
    
    mid = 2 ** (n-1)

    # 1사분면
    if r < mid and c < mid:
        return func(n-1, r, c)

    # 2사분면
    elif r < mid and c >= mid:
        return mid * mid + func(n-1, r, c-mid)

    # 3사분면
    elif r >= mid and c < mid:
        return 2 * mid * mid + func(n-1, r-mid, c)

	# 4사분면
    else:
        return 3 * mid * mid + func(n-1, r-mid, c-mid)

if __name__ == "__main__":
    n,r,c = map(int,input().split())
    print(func(n,r,c))