백준 Z C++

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

1074번: Z

 

이 문제는  1<= N <=15이다. 즉 2차원 배열의 크기가 최대 2^15 * 2^15이기 때문에 2차원 배열을 일일이 순회하면서 답을 구하려고 한다면 시간 초과가 뜰것이다.

 

<풀이>

r과 c가 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 중 하나에 있다. 

1.왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸를 순회

2. 해당칸에 포함 되어 있지 않으면 => cnt += n/2 * n/2

3. 해당칸에 포함 되어 있으면 => 해당 칸에 대해 1번부터 다시

 

 

 

 

 

 

 

#include <iostream>
#include <cmath>
using namespace std;
int N, r, c;
int solve(int n, int cnt, int x, int y)
{
    if (n == 1)
    {
        return cnt;
    }
    pair<int, int> entry[4] = {{x, y}, {x, y + n / 2}, {x + n / 2, y}, {x + n / 2, y + n / 2}};
    for (int p = 0; p < 4; p++)
    {
        int nx = entry[p].first;
        int ny = entry[p].second;
        if (nx <= r && r < nx + n / 2 && ny <= c && c < ny + n / 2)
        {
            if (n == 2)
            {
                for (int i = nx; i < nx + n / 2; i++)
                {
                    for (int j = ny; j < ny + n / 2; j++)
                    {
                        cnt++;
                        if (i == r && j == c)
                        {
                            return cnt;
                        }
                    }
                }
            }
            return solve(n / 2, cnt, nx, ny);
        }
        else
        {
            cnt += n / 2 * n / 2;
        }
    }
    return cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> r >> c;
    int result = solve(pow(2, N), 0, 0, 0);
    cout << result - 1 << "\n";
}