백준_1074 : Z - C++

문제

---

알고리즘

- 분할 정복 알고리즘을 사용하여 풀 수 있는 문제이다.

- 들어 온 좌표가 해당 사분면 안에 있을 경우 그 사분면을 다시 4개의 사분면으로 분할 하여 탐색 하는 과정을 반복 해 준다.

- 존재 하지 않는 경우 size * size 를 ans 에 더해 주는 이유는 다음 사분면의 시작 점이(ex)64) 현재 사분면의 시작점( ex) 0 ) 과 size * size 만큼 차이 나기 때문이다.

- 재귀 호출 도중 x, y 가 문제의 r, c 와 동일 하다면 종료 후 ans 를 출력 해 준다.

---

코드

#include <iostream>
#include <cmath>
using namespace std;

int N, r, c;
int ans = 0;

void Z(int x, int y, int size){
    if(x == c && y == r){ // 정확한 위치를 찾은 경우
        cout << ans;
        return;
    } else if(c < x+size && r < y+size && c >= x && r >= y){// 찾는 r, c 가 현재 4분면 안에 있는 경우
        Z(x, y, size/2);// 그 안에서 1사분면
        Z(x + size/2, y, size/2);// 그 안에서 2사분면
        Z(x, y + size/2, size/2);// 그 안에서 3사분면
        Z(x + size/2, y + size/2, size/2);// 그 안에서 4사분면
    } else {
        ans += size * size;
    }
}

int main(){
    cin >> N >> r >> c;
    Z(0, 0, pow(2, N));
    return 0;
}