[C++] Z (백준 1074번)

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

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int cnt = 0;
vector<vector<int>> m;

void search(int sx, int sy, int size) {
    if (size == 1) {
        m[sy][sx] = cnt++;
        return;
    }
    int div = size / 2;
    search(sx, sy, div);
    search(sx + div, sy, div);
    search(sx, sy + div, div);
    search(sx + div, sy + div, div);
}

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

    int n, r, c;
    cin >> n >> r >> c;

    int msize = pow(2, n);
    m = vector<vector<int>>(msize, vector<int>(msize));

    search(0, 0, msize);

    cout << m[r][c] << '\n';
}

처음에는 모든 결과를 이차원 벡터에 저장해서 메모리 초과가 났다. (오답)

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

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

void search(int sx, int sy, int size) {
    if (size == 1) {
        if (r == sy && c == sx) {
            ans = cnt;
        }
        cnt++;
        return;
    }
    int div = size / 2;
    search(sx, sy, div);
    search(sx + div, sy, div);
    search(sx, sy + div, div);
    search(sx + div, sy + div, div);
}

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

    int n;
    cin >> n >> r >> c;

    int msize = pow(2, n);
    search(0, 0, msize);

    cout << ans << '\n';
}

그래서 배열에 저장하지 않고 ans라는 변수에 저장해서 출력했다. 하지만 시간초과가 났다. (오답)

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

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

void search(int sx, int sy, int size) {
    if (size == 1) {
        if (r == sy && c == sx) {
            ans = cnt;
        }
        cnt++;
        return;
    }
    int div = size / 2;

    if (r < sy + div) {
        if (c < sx + div) {
            search(sx, sy, div);
        } else {
            cnt += div * div;
            search(sx + div, sy, div);
        }
    } else {
        if (c < sx + div) {
            cnt += 2 * div * div;
            search(sx, sy + div, div);
        } else {
            cnt += 3 * div * div;
            search(sx + div, sy + div, div);
        }
    }
}

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

    int n;
    cin >> n >> r >> c;

    int msize = pow(2, n);
    search(0, 0, msize);

    cout << ans << '\n';
}

그래서 구하려는 값의 행과 열을 통해 4분면 중 왼쪽 위인지 오른쪽 위인지 왼쪽 아래인지 오른쪽 아래인지 판단하여 굳이 전부 돌 필요 없는 부분은 그만큼의 값을 cnt에 더해가면서 시간을 줄였다. (정답)