백준 1074번 Z

Z 

문제

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

#include<stdio.h>
#include<iostream>
#include<math.h>

using namespace std;

int x, y;
int cnt=0;

void func(int a, int b, int c, int d, int vol) {
    if (vol==1) {
        if (a == x and b == y) {
            cout << cnt<<endl;
        }
        cnt++;
    }
    else {
        if(x< (a + c) / 2 and y< (b + d) / 2) {
            func(a, b, (a + c) / 2, (b + d) / 2, vol / 4);
        }
        else {
            cnt += vol / 4;
        }
        
        if (x < (a + c) / 2 and y >= (b + d) / 2){
            func(a, (b + d) / 2, (a + c) / 2, d, vol / 4);
        }
        else {
            cnt += vol / 4;
        }
        
        if (x >= (a + c) / 2 and y < (b + d) / 2){
            func((a + c) / 2, b, c, (b + d) / 2, vol / 4);
        }
        else {
            cnt += vol / 4;
        }
        
        if((a + c) / 2<=x and (b + d) / 2<=y){
            func((a + c) / 2, (b + d) / 2, c, d, vol / 4);
        }
        else {
            cnt += vol / 4;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n>>x>>y;
    
    func(0, 0, pow(2, n), pow(2, n), pow(4, n));
}

문제를 보자마자 4분할로 뭔가 계속 나눠서 그 나눈 범위속에 내가 찾는 입력값이 있는지 확인하고 있으면 그 해당 범위를 계속 4분할로 나누어 내가 찾고자 하는 좌표에 도달할때까지 반복하는것이 나의 풀이 방법이었다. 뭔가 더 효율적인 방법이 있을것 같았지만 나는 필라테스때문에(tmi..) 녹초인 상태라 그냥 생각나는대로 구현해보았다.