[백준] 1074번 Z

문제

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

풀이

분할정복과 재귀호출을 통해 해결하는 문제다. 한시간을 넘게 생각했는데 내가 생각한 방식으로 결국 구현을 하지 못했다.

recursion을 구현하는게 너무 힘든 것 같다 ㅠㅠ 하…

관련 강의를 찾아보니까 원리는 이해하겠는데 어떠한 것을 구현하려고 하면 머리가 터질 것 같다.

문제를 구글링 해서 사람들이 올린 소스코드를 봐도 너무 이해하기가 힘들다.

나중에 다시 한 번 풀어봐야겠다.

소스코드

#include <iostream>

using namespace std;

int N, r, c;
int x, y, ans;

void solve(int x, int y,int n) {

    if (x == r && y == c) {
        cout << ans << "\n";
        return;
    }


    if (r < x + n && r >= x && c < y + n && c >= y) 
    {
        solve(x, y, n / 2);
        solve(x, y + n / 2, n / 2);
        solve(x + n / 2, y, n / 2);
        solve(x + n / 2, y + n / 2, n / 2);
    }
    // (r,c)가 현재 사분면이 아니면 그냥 사분면의 크기만큼 더해준다 (탐색한걸로 친다)
    else ans += n* n;

}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> r >> c;

    solve(0, 0, (1 << N));

    return 0;
}