백준 1074번-Z

문제

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

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

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

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

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

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<math.h>
using namespace std;

int num,back_r,back_c,nam;
void z(int N,int r,int c,int cnt) {
	num =(int)pow(2,N)/2;
	nam = (int)pow(pow(2, N - 1), 2);
	if (N == 0) {
		cout << cnt;
	}
	else {
		if (r<num && c< num) {
			z(N - 1, r, c, cnt);
		}
		else if (r<num && c< num*2) {
			cnt += nam;
			z(N - 1, r, c - (int)pow(2, N - 1), cnt);
		}
		else if (r<num*2&& c< num) {
			cnt += nam * 2;
			z(N - 1, r - (int)pow(2, N - 1), c, cnt);
		}
		else{
			cnt += nam * 3;
			z(N - 1, r - (int)pow(2, N - 1), c - (int)pow(2, N - 1), cnt);
		}
	}
}
int main() {
	int N, r, c;
	cin >> N >> r >> c;
	z(N,r, c, 0);
}

정말 어려웠다. 특히 분할정복을 막 공부한지라 단순히 숫자가 작은 부분부터 하나하나 생각하면서 구현하는거구나 라고 생각했는데 이번문제를 통해 틀렸다는것을 깨달았다.

설명을 간단하게 해보면

num은 4분할했을때의 한 정사각형의 변의 길이고

nam은 4분할 했을때의 정사각형 안의 총 갯수

첫번째 if문 부터 순서대로 4분할 했을때 z의 순서로 되어있다.(z의 점을 기준으로 왼쪽위 오른쪽위 왼쪽아래 오른쪽아래 순이다.)

원하는 좌표 r c가 4분면 중에서 어느 위치에 있는지 확인하고 cnt에 누적한다.

각각 분면마다 들어가는 함수인자가 다른이유는 예를들어

N이 3이라 할때

그림 처럼 8*8 크기의 기준의 좌표인 7,7가 4*4 기준으로 바뀔려면 7,7에서 3,3으로 바뀌어야 오버플로우가 안나기때문에

왼쪽위는 상관이 없으므로 그대로

오른쪽위는 오른쪽 7의 값을 3으로

왼쪽아래는 왼쪽 7의 값을 3으로

오른쪽아래는 둘다 3으로 바꿔줘야 하기에 각각 인자가 다르게 들어간다.

이후 N==0일때 더이상 없다는 뜻이므로

cnt의 값을 출력해준다.