cho.shZ
2^N x 2^N 크기 배열을 Z자 순서로 재귀적으로 방문할 때, 주어진 행 r과 열 c의 칸이 몇 번째로 방문되는지 구합니다.
쉬움3분할 정복재귀비트 연산면접 대비아직 제출이 없습니다시간 제한0.5초메모리 제한512 MB문제 설명
예제6
문제
한수는 크기가 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열을 방문하는 순서 번호를 출력한다.
제한
1 <= N <= 150 <= r, c < 2^N