[백준/C++] 1074번: Z

문제

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

---

문제 요약

2^N × 2^N 크기의 2차원 배열을 Z모양으로 탐색하려고 한다.

 

N > 1인 경우, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 탐색한다.

 

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력한다. 

---

코드

#include <iostream>
#include <cmath>

using namespace std;

int N, r, c;

int cnt;

int res;

void fillCount(int n, int x, int y) {
    if (x == r && y == c) {
        res = cnt;
        return;
    }

    else if (x <= r && r < x + n && y <= c && c < y + n) {
        fillCount(n / 2, x, y);
        fillCount(n / 2, x, y + n / 2);
        fillCount(n / 2, x + n / 2, y);
        fillCount(n / 2, x + n / 2, y + n / 2);
    }

    else {
        cnt += n * n;
    }
}

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> r >> c;

    fillCount(pow(2, N), 0, 0);

    cout << res; 

    return 0;
}

---

코드 설명

분할 정복 기법을 이용하여 문제를 해결한다.

 

fillCount(n, x, y)

=> (x, y)를 왼쪽 상단 꼭짓점으로 하는 n × n 크기의 배열을 Z모양으로 탐색하는 함수

 

이 때, 그냥 재귀를 사용하면 시간 초과 문제가 발생한다.

 

따라서, 우리가 원하는 r, c가 현재 탐색 범위에 포함되는지를 파악한다.

 

만약 포함되지 않는다면, 재귀를 이용하지 않고 단순히 해당 범위 크기만큼을 더해준다.

 

< 시간 초과 풀이 >

#include <iostream>
#include <cmath>

using namespace std;

int N, r, c;

int cnt;

int res;

void fillCount(int n, int x, int y) {
    // cout << n << " " << x << " " << y << "\n";

    if (n == 1) {
        if (x == r && y == c) {
            res = cnt;
        }

        else cnt++;
    }

    else {
        fillCount(n / 2, x, y);
        fillCount(n / 2, x, y + n / 2);
        fillCount(n / 2, x + n / 2, y);
        fillCount(n / 2, x + n / 2, y + n / 2);
    }
}

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> r >> c;

    fillCount(pow(2, N), 0, 0);

    cout << res; 

    return 0;
}

---

고찰

cmath include를 통해, pow 함수를 사용할 수 있다.

 

pow(a, b): a의 b제곱 반환