백준 1074 - Z (c++)

백준 1074 - Z

문제 링크

생각 및 접근

• 전형적인 분할 정복 문제다.
• 그런데, 시간 제한이 있으므로 시간을 고려해야 한다.

첫 접근

• 분할 정복을 재귀로 구현해 표를 네 부분으로 나눠서 Z 방향으로 순회하였다.
• 첫 접근으로 cnt 변수를 선언해서 표의 모든 원소를 돌면서 하나씩 늘려가다가, 목표 지점에 도달하면 cnt를 출력하고 끝내려했다.
• 하지만, 시간 초과가 발생했다.

개선

• 네 부분으로 나눠서 탐색할 때, 각 부분에 목표 지점이 없다면, 부분의 원소 갯수만큼 cnt를 늘려주고 그냥 넘어가면 된다. 목표 지점만 탐색하면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

int cnt, N, r, c;

void dc(int size, int x, int y){
    if(size == 1){
        if(x == r && y == c){
            cout << cnt;
            exit(0);
        }
        cnt++;
    }
    else{
        if(x <= r && r <= x + size / 2 && y <= c && c <= y + size / 2)
            dc(size / 2, x, y);
        else
            cnt += pow((size / 2), 2);

        if(x <= r && r <= x + size / 2 && y + (size / 2) <= c && c <= y + size)
            dc(size / 2, x, y + (size / 2));
        else
            cnt += pow((size / 2), 2);

        if(x + (size / 2) <= r && r <= x + size && y <= c && c <= y + size / 2)
            dc(size / 2, x + (size / 2), y);
        else
            cnt += pow((size / 2), 2);

        if(x + (size / 2) <= r && r <= x + size && y + (size / 2) <= c && c <= y + size)
            dc(size / 2, x + (size / 2), y + (size / 2));
        else
            cnt += pow((size / 2), 2);
    }
}

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

    cin >> N >> r >> c;
    dc(pow(2, N), 0, 0);
}

채점 결과