[백준] 1074번 Z - (Python)

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

1074번: Z

분할정복 문제. 2^N x 2^N  사각형을 계속해서 4등분을 해서 해당하는 좌표의 값을 불러오는 문제입니다.여기서 Key포인트는 '모든작업을 하면 안된다' 입니다. Divide & Conquer 방식으로 해당 좌표에 포함되는 부분만 나누어서 문제를 해결해야 메모리초과없이 문제를 해결할 수 있습니다.

분할정복에 대한 개념이 확실히 잡히지 않은상태에서 단순 재귀로 구현해서, 계속된 메모리초과가 발생했었습니다. 따라서 분할정복 개념을 배우고 이를 적용하는 문제로 적합한거 같습니다.

※ 고려사항

1. 분할정복 규칙성 찾기

---

1. 분할정복 규칙성 찾기

해당문제는 좌표가 가리키는 사분면을 1, 2, 3, 4분면으로 구분한 뒤, 계속해서 찾아줘야합니다.

그림을 통해 쉽게 이해해 보겠습니다.

예를 들어, N = 3, r = 0, c = 0 일때, 즉 0의 값을 찾기위한 과정은 다음과 같습니다. 계속해서 4등분을해서, 최종적으로 노란색 사각형이 되면 종료됩니다. 즉, N의 값을 1씩 감소시켜, N = 0이 되었을 경우 종료되게끔 하면 됩니다.

사분면은 다음과 같이 구분합니다. 그림 퀄리티가 낮아서 죄송합니다..

그렇다면 사분면을 구분하는 규칙은 무엇일까요? 다음 그림을 통해 이해해봅시다.

왼쪽 이미지는 N=3, 16의 배수로 오른쪽 이미지는 N=2. 4의 배수로 이루어짐.

즉, 2^(n-1) x 2^(n-1) x (0, 1, 2, 3) 으로 이루어집니다. 따라서 다음과 같이 정리할 수 있습니다.

0 : 1사분면, 1: 2사분면, 2 : 3사분면, 3 : 4사분면

왼쪽 이미지에서 4사분면 48은 N=3이므로 계산해보면 2^2 x 2^2 x 3 = 4 x 4 x 3 = 48입니다.

 

따라서 N을 1씩 줄여나가면서 해당 좌표가 해당하는 사분면만 계속해서 계산해주면 됩니다.

그렇다면 좌표를 구별하는 특징을 살펴보겠습니다.

사분면이 바뀌는 경계점을 고려합니다. N = 2일때는 (0, 0), (2, 0), (0, 2) (2, 2) 즉, N의 값을 넘으면 사분면이 바뀌게 됩니다. 또 계속해서 N이 줄어듬에 따라 사각형이 줄어들기 때문에, 우리가 찾으려는 좌표도 수정해야 합니다.

 

예를들어, N = 3, (7, 7)의 좌표는 63입니다. 해당좌표는 4사분면에 있기 때문에, 4사분면 사각형만 고려합니다. 그렇게 되면 다음 그림과 같이 됩니다. 

(7, 7) -> (3, 3)

(7, 7) 의 좌표가 (3, 3) 으로 줄고 N = 2가 되었습니다. 즉. 2^N 만큼 좌표가 줄어들게 됩니다. 

이제 코드를 통해 확인해봅시다.

import sys

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

cnt = 0

while n != 0:

    n -= 1

    # 1사분면
    if c < pow(2, n) and r < pow(2, n):     # 사분면 구별
        cnt += pow(2, n) * pow(2, n) * 0    # 숫자 규칙
    
    # 2사분면
    elif c < pow(2, n) and r >= pow(2, n):  
        cnt += pow(2, n) * pow(2, n) * 1     
        r -= pow(2, n)                      # 좌표 변경 규칙
    
    # 3사분면
    elif c >= pow(2, n) and r < pow(2, n):
        cnt += pow(2, n) * pow(2, n) * 2
        c -= pow(2, n)
    
    # 4사분면
    else:
        cnt += pow(2, n) * pow(2, n) * 3
        c -= pow(2, n)
        r -= pow(2, n)
print(cnt)

---

해당문제를 단순히 재귀로 구현하여, 메모리 초과가 발생했습니다.

메모리초과 코드

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10000)
n, c, r = map(int, input().split())
matrix = [[0] * pow(2,n) for _ in range(pow(2,n))]

cnt = 0
def z(n, x, y):

    global cnt
    real_y = y
    if n == 1:
        for _ in range(pow(2, n)):
            for _ in range(pow(2, n)):
                matrix[x][y] = cnt
                y+=1
                cnt+=1
            x+=1
            y = real_y
        return

    else:
        z(n-1, x, y)
        z(n-1, x, y + pow(2,n-1))
        z(n-1, x + pow(2, n-1), y)
        z(n-1, x + pow(2, n-1), y + pow(2, n-1))

z(n, 0, 0)
print(matrix[c][r])

분할정복의 개념을 자료구조 Divide & Conquer으로 학습했으나, 코드로 구현하기에는 또 어려움이 있었습니다. 분할정복 문제는 반드시 많이 연습하여 체화시켜야 한다고 느낀 문제였습니다. 시간초과나 메모리 초과를 해당 방법으로 구현하지 못하면 반드시 피할 수 없기 때문입니다. 다른 분할정복 문제로 다시 찾아오겠습니다.

설명의 오류나, 궁금하신점은 언제든 피드백 해주시면 감사하겠습니다 ^~^