[BOJ] 1074번 | Z (C++)

🔗문제 보러가기

1074번: Z

 

👨‍💻풀이 과정

 

처음에 문제를 보고 별 생각없이 배열 선언하고 분할 정복을 했다가 메모리 초과. (\( 2^{15} \times 2^{15} \))

배열 없이 카운팅 변수 하나로만 아무 생각없이 셌다가 시간 초과. (하나씩 돌면서 점검하면 결국 \(\mathrm{O( 2^{15} \times 2^{15})}\))

 

그래서 4등분을 하고, 찾고자 하는 (행, 열)이 해당 칸에 없는 경우에는 사각형 개수만큼 더해 주었습니다.

만약 찾고자 하는 (행, 열)이라면, 해당 칸에 대해서만 다시 재귀적으로 들어가는 로직을 구성해 풀 수 있었습니다.

 

예를 들어, \(4 \times 4 \) 크기의 사각형에서 찾고자 하는 칸이 \((3, \ 1)\) 이라면,

 

 

\(4 \times 4 \) 크기이므로 4등분을 하면, 한 변의 길이가 2인 사각형이 4개가 만들어 집니다.

 

 

Z 모양으로 순회를 해야 하므로, 왼쪽 위 👉🏻 오른쪽 위 👉🏻 왼쪽 아래 👉🏻 오른쪽 아래 순으로 열 방향 탐색을 진행합니다. 왼쪽 위 사각형과 오른쪽 위 사각형에는 우리가 찾는 칸이 없으므로, 왼쪽 위 사각형 넓이(4) + 오른쪽 위 사각형 넓이(4) = 8 을 카운팅 변수에 더해 줍니다.

 

왼쪽 아래 사각형에는 찾고자 하는 칸이 있으므로, 여기에 대해 다시 4등분하는 재귀를 적용해줍니다.

*(오른쪽 아래 사각형은 이제 볼 필요가 없으므로 검사 X)

 

등분한 사각형이 한 칸이 될 때까지 적용하며, 찾고자 하는 칸을 찾았다면 재귀를 종료하고 출력하면 됩니다.

 

 

✏️소스 코드 및 결과

#include <iostream>
#include <cmath>

using namespace std;
#define FAST_IO ios::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

int N, r, c;

void Traversal(int sideLength, int row, int col, int& order) {
    if (sideLength < 2)
        return;
    
    int halfLength = sideLength / 2;

    for (int ri = row; ri < row + sideLength; ri += halfLength) {
        for (int ci = col; ci < col + sideLength; ci += halfLength) {
            bool isExistInCurrentSquareWidth = (ci <= c and c < ci + halfLength);
            bool isExistInCurrentSquareHeight = (ri <= r and r < ri + halfLength);

            if (isExistInCurrentSquareWidth and isExistInCurrentSquareHeight) {
                Traversal(halfLength, ri, ci, order);
                return;
            }
            
            order += halfLength * halfLength;
        }
    }
}


int main() {
    FAST_IO
    cin >> N >> r >> c;

    N = static_cast<int>(pow(2, N));
    int order = 0;

    Traversal(N, 0, 0, order);
    cout << order;

    return 0;
}