[백준]Z(분할정복)다시풀어보자

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

1074번: Z

 

어떤 천재의 풀이를 이해만 했다... 재귀를 써야하나 여러가지 방법을 생각했지만 2^15까지의 배열의 크기가 나오는

문제이다. 분할정복이란 가장 최소의 단위까지 분할을 하고 문제를 처리해주는 것이다.

분할은 쪼개주면서 하는 것이고 이제 그것들을 어떻게 활용해서 답을 구할지를 구현해야한다..(정복!!)

 

#include <iostream>
#include <cmath>
using namespace std;
 
int N, r, c;
int cnt = 0;;
 
void solve(int y, int x, int jump) {
    if (y == r && x == c) { //최소의 분할에서 구하고하는 값과 일치.
        printf("%d\n", cnt);
        return;
    }
    //구하고자하는 점이 속한 영역을 계속 분할
    //else의 경우에서 값을 업데이트 하기때문에 순서가 중요함 Z순서로 함수순서구성.**
    if ((x <= c && c < x + jump) && (y <= r && r < y + jump)) {
        solve(y, x, jump / 2);
        solve(y, x + jump / 2, jump / 2);
        solve(y + jump / 2, x, jump / 2);
        solve(y + jump / 2, x + jump / 2, jump / 2);
    }//구하고자하는 점이 속하지 않는 곳은 빠르게 값만 업데이트하고 리턴.
    else {
        cnt += jump * jump;
        return;
    }
}
 
int main()
{
    cin >> N >> r >> c;
    N = pow(2, N);
    solve(0,0,N);
    return 0;
}