(C++) 백준 1074번 - Z

풀이

재귀를 이용하여 풀이하였다.

2의 거듭제곱으로 커져가기 때문에 한 변의 길이가 2, 4, 8, 16, ... 순으로 증가한다.

그렇기 때문에 한 변이 2일 때를 재귀를 종료하는 base condition으로 두고, 사각형들을 4개로 분할하여(한 변의 길이를 2배씩 줄여) 나가면서 풀었다.

#include <iostream>

using namespace std;

int calZ(int n, int r, int c){
    if(n == 1){ // 2 * 2 일 때
        if(r == 0 and c == 0) return 0;
        else if(r == 0 and c == 1) return 1;
        else if(r == 1 and c == 0) return 2;
        else return 3;
    }
    int half = (1<<n)/2; // (2^n) / 2
    if(r < half and c < half) return calZ(n-1, r, c); // 4분할 했을 시에 첫번째 사각형
    else if(r < half and c >= half) return half*half+calZ(n-1, r, c-half); // 두번째 사각형
    else if(r >= half and c < half) return 2*half*half+calZ(n-1, r-half, c); // 세번째 사각형
    else return 3*half*half+calZ(n-1, r-half, c-half);  // 네번째 사각형
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    int n, r, z;
    cin >> n >> r >> z;
    cout << calZ(n, r, z);
}