[백준 1074] Z with Python

문제 링크

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

1074번: Z

풀이

def Z(N, r, c, nth):
    if N == 0: return nth
    hf = 2**(N-1)
    if r < hf and c < hf:
        return Z(N-1, r, c, nth)
    elif r < hf and c >= hf:
        return Z(N-1, r, c-hf, nth+hf**2)
    elif r >= hf and c < hf:
        return Z(N-1, r-hf, c, nth+(hf**2)*2)
    else:
        return Z(N-1, r-hf, c-hf, nth+(hf**2)*3)

N, r, c = map(int, input().split())
print(Z(N, r, c, 0))

이 문제는 주어지는 입력값이 매우 크고, 제한 시간이 짧기 때문에 리스트를 만들어서 숫자를 나열한 후에 (r, c)에 있는 숫자를 출력하는 방식으로는 통과할 수 없다.

 

대신에, 현재 배열을 4분할 하였을 때 좌표(r, c)가 4개 중 어디에 위치하는가를 찾으면서 해당 사분면의 최솟값을 계속 누적하는 방식으로 해결하였다.

 

예를 들어, N=3, r=6, c=5라는 입력값이 주어졌을 때, ((0, 0)=0, (7, 7)=63, (6, 5)=57)

Z(3, 6, 5, 0)을 호출하면

위 배열에서 (6, 5)는 우측 하단에 위치하므로

Z(2, 2, 1, 48)이 호출된다.

이 때, 48부터 시작하는 배열은 원래 0부터 시작하는 N=2인 배열로 간주한다.

 

위 배열에서 (2, 1)은 좌측 하단에 위치하므로

Z(1, 0, 1, 56(48+8))이 호출된다.

 

(8부터 시작하는 배열을 원래 0부터 시작하는 N=1인 배열로 간주하였다)

 

위 배열에서 (0, 1)은 우측 상단에 위치하므로

Z(0, 0, 0, 57(56+1))이 호출된다.

Z는 N=0일 때 nth를 반환하고 재귀호출이 종료된다.

따라서 57을 반환한다.