CodeDrive

문제:

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

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

다음은 N=3일 때의 예이다.

입력:

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

출력:

r행 c열을 몇 번째로 방문했는지 출력한다.

풀이방법:

시간 제한이 생각보다 많이 빡세기 때문에, 분할 정복을 사용하더라도 좀 더 효율적인 방법이 필요하다. 따라서 r, c 좌표를 통해서 해당 영역으로 찾아들어가는 방식을 사용하도록 한다.

모든 영역은 2^N-1 영역으로 4등분하며 순서대로 방문하기 때문에 r과 c가 이렇게 나눈 영역에서 어느 곳에 속하는지 알면 된다.

우선 나눠지는 순서대로 왼쪽 위를 0번째, 오른쪽 위를 1번째, 왼쪽 아래를 2번째, 오른쪽 아래를 3번째라고 하자

 1. 0번째 영역에 속하기 위해서는 r과 c가 모두 2^(N-1)보다 작아야 한다. 그리고 0번째 영역의 첫 숫자는 항상 0이기 때문에 시작 값에 대한 변화가 없다.

 2. 1번째 영역에 속하기 위해서는 r은 2^(N-1)보다 작으며, c는 커야 한다. 1번째 영역의 왼쪽 위 첫 숫자는 4^(N-1)*1에 해당한다. (총 숫자는 2^N*2^N= 4^N 개 있으며, 이를 사등분 하면 각 영역당 숫자는 4^(N-1)개 있다.)

 3. 2번째 영역에 속하기 위해서는 r은 2^(N-1)보다 크며, c는 작아야 한다. 첫 숫자는 4^(N-1)*2이다.

 4. 3번째 영역에 속하기 위해서는 r과 c가 모두 2^(N-1)보다 커야 한다. 첫 숫자는 4^(N-1)*3이다.

위 4개 비교를 통해서 각 영역에 들어가기 위해 r과 c를 2^(N-1)보다 크다면 그 값을 빼주고, N=1이 될 때까지 반복한다.

최종적으로는 r과 c는 0아니면 1에 해당하는 제일 작은 Z를 얻을 수 있고, 해당하는 영역의 숫자를 answer에 더해 출력해주면 된다.

문제링크:

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