Z

면접 대비

시간 제한0.5초메모리 제한512 MB

요약

2^N x 2^N 크기 배열을 Z자 순서로 재귀적으로 방문할 때, 주어진 행 r과 열 c의 칸이 몇 번째로 방문되는지 구합니다.

문제

한수는 크기가 2^N x 2^N인 정사각형 배열을 Z 순서로 방문하려고 한다. 2 x 2 배열에서는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순서로 칸을 방문하며, 이 순서가 Z 모양이다.

N > 1이면 배열을 크기가 2^(N-1) x 2^(N-1)인 네 개의 부분 배열로 나눈 뒤, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 부분 배열을 차례로 같은 방식으로 재귀적으로 방문한다.

아래 그림은 2^2 x 2^2 크기의 배열에서 각 칸을 방문하는 순서를 보여준다.

N, r, c가 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

아래 그림은 N = 3인 경우의 방문 순서를 보여준다.

첫째 줄에 정수 N, r, c가 주어진다.

r행 c열을 방문하는 순서 번호를 출력한다.