백준 1074번 Z (C++)

문제 난이도 :  골드 5

문제 유형 : 재귀, 분할 정복

문제 해결 방법 : 계속 하나의 면이 4개의 면으로 나눠진다는 재귀적 성질을 이용해서 문제를 해결했다. 직접 인덱싱을 해서 해결하는 건 너무 까마득해서 재귀성을 이용해야 그나마 쉽게 풀 수 있다. 4개의 면중 하나에 해당된다는 걸 확인하고 나머지 면은 버리고 한 면에 대해서 다시 조사한다. 이때, 면을 버리면서 내가 지날 수 밖에 없는 사분면 칸 만큼을 freq에 더해 준다.이를 더 이상 조사할 수 없을 때까지 반복한다.

문제 해결 소감 : 대략적인 아이디어를 파악해도 코드 작성 과정에서 정확하게 코드를 짜지 않으면 결과가 확 달라져 버린다.ㅠㅠ half를 std::pow(2,n-1)+1로 하고 area만큼 더하도록 처음에 코드를 짰었는데 왜 아닌지를 생각하는게 오래 걸렸다.

#include <iostream>
#include <cmath>
int N;
int r, c;
int freq;
void Findquad(int n, int p, int q);
int main(void)
{
    std::cin >> N;      // 1<=N<=15 2^N * 2^N
    std::cin >> r >> c; // r행 c열
    Findquad(N, r, c);
}
void Findquad(int n, int p, int q) // N의 수만큼 반복하면 된다
{
    if (n == 0)
    {
        std::cout << freq;
        return;
    }
    int half = std::pow(2, n - 1);
    int area = std::pow(2, 2 * n - 2);
    if (p < half && q < half) // 2사분면
    {
        freq += 0;
        Findquad(n - 1, p, q);
    }
    else if (p < half && q >= half) // 1사분면
    {
        freq += area;
        Findquad(n - 1, p, q-half);
    }
    else if (p >= half && q < half) // 3사분면면
    {
        freq += (area * 2);
        Findquad(n - 1, p-half, q);
    }
    else if (p >= half && q >= half) // 4사분면
    {
        freq += (area * 3);
        Findquad(n - 1, p-half, q-half);
    }
}