[백준 / 1074] Z - Python

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

1074번: Z

<풀이>

처음에는 해당 표를 리스트로 그려서 풀었더니 메모리 초과가 나왔다. (그럴만도 했다..)

그래서 구현하지 않는 풀이를 생각하기 위해서 규칙을 찾았다.

 

n=3인 경우 각 사분면의 시작은 0, 16, 32, 48이다.

n=2인 경우 각 사분면의 시작은 (0, 4, 8, 12), (16, 20, 24, 28), (32, 36, 40, 44), (48, 52, 56, 60)

...

 

따라서 재귀식으로 범위를 좁혀가면서 해당 위치의 값을 찾아내면 된다.

3 7 7 입력의 경우 n=3인 경우 4사분면에 있고, n=2인 경우 4사분면에 있고, n=1인 경우 4사분면에 있다.

 

<전체 코드>

def z(n, row, col, start=0):
    if n == 0:
        return start
    else:
        gap = 4**(n-1)
        side1 = start
        side2 = start+gap
        side3 = start+2*gap
        side4 = start+3*gap

        if row < (2**n)/2 and col < (2**n)/2:
            return z(n-1, row, col, side1)
        elif row < (2**n)/2 and col >= (2**n)/2:
            return z(n-1,  row, col-(2**n)/2, side2)
        elif row >= (2**n)/2 and col < (2**n)/2:
            return z(n-1, row-(2**n)/2, col, side3)
        else:
            return z(n-1, row-(2**n)/2, col-(2**n)/2, side4)


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