[백준] 1074. Z - 파이썬

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

 

풀이

재귀함수, 분할정복(Divide and Conquer)를 통해 어렵지 않게 풀 수 있었던 문제.

 

각 단계마다 4개의 구역으로 나누어, 어느 구역에 있는 지를 확인하고,

크기를 다시 1/4로 줄여 어느 구역에 있는 지를 확인하는 과정을 반복하면 된다.

 

와 같은 경우, N=2일 때 1행 3열의 숫자인 7을 구하는 과정은 (0행 0열이 start.)

 

sol(2, 3, 1) 에서 middle = 2 이므로, r >= middle, c < middle.

r >= middle 이므로 r = r - middle = 1

그리고 1구역이므로, 1x4 = 4 에, sol(N-1, r, c) 을 재귀호출하여 더해준다.

호출된 sol(1, 1, 1) 에서는 middle = 1 이며, 3구역. 따라서 3을 return.

결국 최종적으로 return되는 값은 1x4+3 = 7.

이런 식으로 N이 커져도 재귀호출을 통해 계산 가능.

 

이 문제에서 유의할 점은, r, c (행, 열)의 입력 순서에 주의할 것.

 

Num, col, row = map(int, input().split())

def A(N, r, c):
    middle = pow(2, N-1)
    if r < middle and c < middle:
        return 0
    elif r >= middle and c < middle:
        return 1
    elif r < middle and c >= middle:
        return 2
    elif r >= middle and c >= middle:
        return 3

def sol(N, r, c):
    if N == 1:
        return A(N, r, c)

    middle = pow(2, N-1)
    area = A(N, r, c)
    if r >= middle:
        r -= middle
    if c >= middle:
        c -= middle

    return area*(int(pow(pow(2, N), 2) / 4)) + sol(N-1, r, c)

print(sol(Num, row, col))