한수는 크기가 2N × 2N인 2차원 배열을 Z 모양으로 탐색하려고 한다. 예를 들어, 2 × 2 배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z 모양이다.
만약, N > 1이 나서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다. 다음 예는 22 × 22 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오. 다음은 N=3일 때의 예이다.
설명
상당히 재귀적인 특성을 지니고 있다. 정사각형 배열이며 배열을 4 사분면으로 나누었을 때 2 사분면, 1 사분면, 3 사분면, 4 사분면 순으로 방문한다.
r행 c열이 몇 사분면에 있냐에 따라 몇 번째에 방문할지 확인할 수 있다. n=1일 때 2 사분면에 있다면 0번째로 방문할 것이다. 1 사분면에 있다면 1번째로 방문할 것이며 4 사분면에 있다면 3번째로 방문할 것이다.
만약 n=3이고 r행 c열이 4 사분면에 있다면 이미 1,2,3 사분면을 지나온 것이기 때문에 최소 48개의 배열을 지나온 것이다. 더 구체적인 방문 횟수를 구하기 위해서는 r행 c열이 4 사분면에서 어느 사분면에 있는지를 확인해야 한다.
그렇기 때문에 사각형을 4 사분면으로 축소해서 r행 c열을 새로운 r과 c로 동기화해주어야 한다. 예를 들어 n=3일 때 r행 c열이 4 사분면에 있었다면 사각형을 4 사분면으로 축소한 후 r과 c에서 2^(n-1)인 4만큼 빼준다.
이 작업을 n이 0이 될 때까지 반복한다.
전체 사각형에서 r행 c열이 몇 사분면에 있는지 파악
r행 c열이 있는 사분면에 따라 최소 방문 횟수를 더해줌
사각형 축소(n--) 및 r행 c열 동기화
n이 0이 될 때까지 반복
코드
#1074번 Z
if __name__ == "__main__":
n,r,c = map(int,input().split()) # 3 7 7 -> 63
result = 0
while n :
mid = 2**(n-1)
if mid > r and mid > c :
result += 0
elif mid > r and mid <= c :
result += mid*mid
c -= mid
elif mid <= r and mid > c :
result += mid*mid*2
r -= mid
elif mid <= r and mid <= c :
result += mid*mid*3
c -= mid
r -= mid
n -= 1
print(result+c+r)
