[BOJ/백준 1074][C++] Z

문제

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

백준 1074

백준 1074

 

문제 내용

사진에 보이는 것처럼 방문을 한다고 할 때, r, c를 방문했을 때의 값을 구하면 된다.

 

문제 풀이

2^N * 2^N 크기의 2차원 배열을 4등분하여 r, c가 어느 사분면에 속해있는지 체크하고 똑같이 재귀적으로 계산해 나가면 된다.

 

코드

#include <iostream>
using namespace std;

int visit(int N, int r, int c) {
    if (N == 0) { // N이 0인경우 배열 자체가 없음
        return 0;
    }

    int length = (1 << (N - 1));
    if (r < length && c < length) { // 1사분면
        return visit(N - 1, r, c);
    } else if (r < length && c >= length) { // 2사분면
        return visit(N - 1, r, c - length) + length * length;
    } else if (r >= length && c < length) { // 3사분면
        return visit(N - 1, r - length, c) + 2 * length * length;
    } else { // 4사분면
        return visit(N - 1, r - length, c - length) + 3 * length * length;
    }
}

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

    cout << visit(N, r, c);
}