백준 1074번 Z

🔒[문제 url]

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

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <cmath>
using namespace std;

int n, r, c;
int ans = 0;

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> r >> c;
}

void Z(int x, int y, int size)
{
    // r행 c열을 방문한 경우
    if (x == r && y == c)
    {
        cout << ans;
        return;
    }
    
    // r행 c열이 현재 탐색중인 범위 내에 있다면, 사분면으로 나누어 탐색
    if (x <= r && r < x + size && y <= c && c < y + size)
    {
        int halfSize = size / 2; // 탐색 범위를 절반으로 줄임

        /* 그림 순서대로 이동해야함에 주의한다. */

        // Left Up
        Z(x, y, halfSize);
        // Right Up
        Z(x, y + halfSize, halfSize);
        // Left Down
        Z(x + halfSize, y, halfSize);
        // Right Down
        Z(x + halfSize, y + halfSize, halfSize);
    }
    // 현재 탐색 범위에 r행c열이 없다면, 현재 탐색범위의 크기만큼 더해줌
    else ans += size * size;
}

void SOLVE()
{
    // 전체 범위부터 좁혀가며 탐색 => 분할 정복
    Z(0, 0, pow(2, n));
}


int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.