[백준 c++] 1074 Z

문제

https://www.acmicpc.net/problem/1074
2^N × 2^N인 2차원 배열을 Z모양으로 탐색할 때
r행 c열을 몇 번째로 방문하는지 구하는 문제다.

---

풀이

1 ≤ N ≤ 15 라서 전체 탐색을 하면
2^15 x 2^15 = 약 10억 번의 연산이 필요하므로 재귀를 통해 중간중간 건너 뛰는 풀이가 필요하다.

처음에는 N의 1/4 크기만큼 온전히 구한다음에 몇 번째 4분면에 속하는지에 따라 가중치를 더하면 되려나 했는데
그렇게 하면 어쨌든 1/4만큼 배열로 저장을 해야했고 N=15일 경우 약 2억의 연산이 필요하므로 불가능했다.

재귀로 푸는 것도 알겠고 4등분 해가면서 푸는건 알겠는데 그래서 그 방문 순서는 배열을 안쓰고 어케 구하지? 고민하다가 결국 다른 블로그를 참고했다^.^

무릎탁!🙀

1. 4등분으로 나눠 탐색한다.
2. 해당 사분면에 (r,c)가 속하면 다시 4등분 탐색
3. 해당 사분면에 (r,c)가 속하지 않는다면 방문순서 += (size x size)

건너뛴 블록의 size x size만큼을 더하면 그 다음 블록 시작의 방문 순서가 되는 것이다!

재귀는 아직도 어렵다🦔

---

코드

#include <iostream>
using namespace std;
int n, r, c, ret;

void go(int y, int x, int size)
{
    if ((y == r) && (x == c))
    {
        cout << ret << "\n";
        return;
    }
    if ((y <= r && r < y + size) && (x <= c && c < x + size))
    {
        go(y, x, size / 2);
        go(y, x + size / 2, size / 2);
        go(y + size / 2, x, size / 2);
        go(y + size / 2, x + size / 2, size / 2);
    }
    else
    {
        ret += size * size;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> r >> c;
    go(0, 0, (1 << n));
}