[백준] 1074번 Z

문제 링크: https://www.acmicpc.net/problem/1074

문제

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

문제 이해

분할 정복문제이다.
4등분으로 나누어 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 방문하는 것이다. 해당 방문은 분할할 때 순서로 설정하면 쉽게 구현 가능하다.
전에 구현했던 분할 정복문제랑 비슷하게 구현하면, 이 문제는 시간 초과가 난다. 그래서 모든 부분을 탐색할 필요가 없다. (r,c)부분만 구하면 되기 때문에 (r,c)가 속한 부분을 더 자세히 찾으면 된다.
구역이 들어오면, 해당 구역내에 (r,c)가 속하는 지 체크한다. 만약 해당 구역에 존재하면, 해당 구역을 4부분 나눈다. 만약 해당 구역에 속하지 않는다면, 해당 구역의 크기만큼 탐색한 수에 더해준다.

코드 구현(c++)

#include <iostream>

using namespace std;



int N,r,c;
int cnt = 0;
int result;

int pow(int base, int num){
    if(num == 1) return base;
    else return base * pow(base, num - 1);
}
void divide(int x, int y, int n){
    if(r == y && c == x){
        result = cnt;
        return; 
    }
    if(r < y + n && r >= y && c < x + n && c >= x){
        divide(x, y, n/2);//왼위
        divide(x + n/2, y, n/2);//오위
        divide(x, y + n/2, n/2);//왼아
        divide(x + n/2, y + n/2, n/2);//오아
    }
    else{
        cnt += n * n;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    cin >> N >> r >> c;
    divide(0, 0, pow(2, N));

    cout << result << "\n";
}