[백준] 1074번 Z C++ 코드

코드

#include <iostream>

using namespace std;

int n,r,c;

// 2**n칸
// r행 c열 몇 번째 방문?

int go(int size, int row, int col) {
    // 기저조건
    if(size == 1) {
        return 0;
    }

    // 탐색
    int halfSize = size / 2;
    int quadrantSize = halfSize * halfSize;
    if(row < halfSize && col < halfSize) {
        return go(halfSize, row, col);
    } else if(row < halfSize && col >= halfSize) {
        return quadrantSize + go(halfSize, row, col - halfSize);
    } else if(row >= halfSize && col < halfSize) {
        return quadrantSize * 2 + go(halfSize, row - halfSize, col);
    } else if(row >= halfSize && col >= halfSize) {
        return quadrantSize * 3 + go(halfSize, row - halfSize, col - halfSize);
    }
}

int main() {

    cin >> n >> r >> c;
    int len = (1 << n);
    cout << go(len, r, c) << '\n';

    return 0;
}

풀이

칸의 크기가 2^n이라서 분할정복을 이용해 해결할 수 있었다. 만약 목표한 점보다 반으로 자른 길이가 긴 경우와 작은 경우를 나눠서 좌상, 우상, 좌하, 우하 케이스를 나눈다. 좌상의 경우는 사각형의 개수가 0개, 우상의 경우는 1개, 좌하의 경우는 2개, 우하의 경우는 3개가 있다. 사각형의 개수를 더해가면서 몇 번째 행, 열에 있는지 탐색해 나가면 된다.

 

halfsize보다 긴 경우에 행, 열 값에서 halfsize값을 빼주는 이유는 작아진 사각형에서 위치를 찾아낼 수 있게 하기 위함이다.