Z 1074

문제

접근 방법

1개의 범위는 4개의 범위로 나뉜다.
1개의 크기가 될 때까지 나눠줄 수도 있지만 시간을 절약하려면 굳이 탐색하지 않아도 되는 부분은 탐색 안 하면 된다.

그러한 부분은 무엇이냐면 범위를 초과하는 부분이다.

코드

#include <iostream>
using namespace std;
int N, r, c;
int recur(int startX, int endX, int startY, int endY, int depth)
{
    if (depth == -1)
        return 1;
    int midX = (startX + endX) >> 1;
    int midY = (startY + endY) >> 1;
    int val = 1 << depth;
    val *= val;
    int sum = 0;
    if (midX <= c || midY <= r)
    {
        sum = val;
        if (midY <= r)
        {
            sum += val;
            if (midX <= c)
            {
                sum += val;
                return sum += recur(midX, endX, midY, endY, depth - 1);
            }
            else
                return sum + recur(startX, midX, midY, endY, depth - 1);
        }
        else
            return sum + recur(midX, endX, startY, midY, depth - 1);
    }
    else
        return recur(startX, midX, startY, midY, depth - 1);
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> r >> c;
    int end = 1 << N;
    cout << recur(0, end, 0, end, N - 1) - 1;
    return 0;
}

풀이

미리 범위의 크기를 구한 뒤 범위를 넘으면 더해주고 해당하면 탐색하고 벗어나면 무시해 준다.