[백준] 1074번 Z - Python / 알고리즘 중급 1/3 - 분할 정복 (연습)

---

---

---

💡 문제

한수는 크기가 2$^N$ × 2$^N$인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2$^{N-1}$ × 2$^{N-1}$로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2$^2$ × 2$^2$ 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

---

💭 접근

이 문제에서 주어진 그림을 보면 규칙을 하나 발견할 수 있다. 아래는 n이 3일 때의 그림이다.

우선, 4개의 사분면으로 나눌 수 있는 것을 볼 수 있는데, 각 사분면 마다 1사분면을 기준으로 16, 32, 48만큼 더해져 있는 것을 볼 수 있다.

이제 더 작은 영역을 보자. 아래는 n이 2일 때의 그림이다.

또 4개의 사분면으로 나누었을 때, 각 사분면마다 1사분면을 기준으로 4, 8, 12만큼 더해져 있는 것을 볼 수 있다.

따라서 입력으로 주어진 r, c가 몇 사분면에 속하는 지 구한 뒤, 현재 n에 따라 정답을 더해준 후, n의 크기를 줄이고 r과 c도 각 사분면 위치에 따라 갱신해 준 뒤, n이 1보다 클때까지 반복해주면 된다.

---

📒 코드

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

ans = 0
n = 2**n
while n > 1:
    if 0 <= r < n//2 and 0 <= c < n//2: # 1사분면
        pass
        
    elif 0 <= r < n//2 and n//2 <= c < n: # 2사분면
        ans += 1 * (n//2) ** 2
        c -= n//2
        
    elif n//2 <= r < n and 0 <= c < n//2: # 3사분면
        ans += 2 * (n//2) ** 2
        r -= n//2
        
    elif n//2 <= r < n and n//2 <= c < n: # 4사분면
        ans += 3 * (n//2) ** 2
        r -= n//2
        c -= n//2
    n //= 2
print(ans)

---

💭 후기

분할 정복 문제는 반드시 재귀로만 해결하는 줄 알았지만, 그 편견을 깨준 문제였다.

---

🔗 문제 출처

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

---