Z

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초	512 MB	56813	21714	16372	39.511%

문제

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다.

예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2^N-1 × 2^N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

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

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2^N

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

예제 입력 3

1 0 0

예제 출력 3

0

예제 입력 4

4 7 7

예제 출력 4

63

예제 입력 5

10 511 511

예제 출력 5

262143

예제 입력 6

10 512 512

예제 출력 6

786432

출처

• 문제를 번역한 사람: baekjoon
• 잘못된 조건을 찾은 사람: hmw9309

알고리즘 분류

• 분할 정복
• 재귀

---

통과된 코드

#include <iostream>
#include <cmath>

using namespace std;

int N, r, c, cnt, result;

// (넓이, 시작 x 좌표 , 시작 y 좌표)
void DivideAndConquer(int w, int x, int y)
{
	if (w == 1) {
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++){
				if (x + i == r && y + j == c ) result = cnt;
				cnt++;
			}
		}
		return;
	}
	
	// R, C 의 위치를 각 4분면으로 나누어서 
	// 해당 위치에 없다면 재귀함수로 진입하지않고 계산으로 시간 단축
	if (result == 0) { // 결과가 정해지면 더이상 진행하지 않는다.
		if (x + pow(2, w - 1) > r && y + pow(2, w - 1) > c) DivideAndConquer(w - 1, x, y); // 2
		else  cnt += pow(pow(2, w - 1), 2);

		if (x + pow(2, w - 1) > r && y + pow(2, w - 1) <= c) DivideAndConquer(w - 1, x, y + pow(2, w - 1)); // 1
		else  cnt += pow(pow(2, w - 1), 2);

		if (x + pow(2, w - 1) <= r && y + pow(2, w - 1) > c) DivideAndConquer(w - 1, x + pow(2, w - 1), y); // 3
		else  cnt += pow(pow(2, w - 1), 2);

		if (x + pow(2, w - 1) <= r && y + pow(2, w - 1) <= c) DivideAndConquer(w - 1, x + pow(2, w - 1), y + pow(2, w - 1)); // 4
		else  cnt += pow(pow(2, w - 1), 2);

	}
}

int main()
{
	ios_base::sync_with_stdio(false); // scanf와 동기화를 비활성화
	// cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
	cin.tie(NULL);
	cout.tie(NULL);

	cnt = 0;
	result = 0;

	cin >> N >> r >> c;
	
	// 분할 정복
	DivideAndConquer(N, 0, 0);

	cout << result;

	return 0;
}