Z

코드

(시간초과 풀이)

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

int N, r, c, ans=-1;
void find(int i, int j, int depth){
    if(depth == 1){
        for(int q=i-1;q<=i;q++)
        {
            for(int z=j-1;z<=j;z++)
            {
                ans++;
                if(q == r and z == c) 
                    cout << ans << '\n';
            }
        }
    }
    else{
        find(i/2, j/2, depth-1);
        find(i/2, j, depth-1);
        find(i, j/2, depth-1);
        find(i,j, depth-1);
    }
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> r >> c;
    find((int)pow(2,N)-1, (int)pow(2,N)-1, N);
    return 0;
}

• 각 범위를 depth로 두고 타고 들어가서 차례대로 수행하게 하였음
• 모든 범위에 대해 수행하므로 0.5초 시간동안 수행할 수 없음

---

(정답 풀이)

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

int N, r, c, ans;
void find(int i, int j, int size){
    if(i == r and j == c)
    {
        cout << ans << '\n';
        return;
    }
    if((r >= i and r< i+size) and(c >= j and c < j+size)){
        /* 1사분면 탐색 */
        find(i, j, size/2);
        /* 2사분면 탐색 */
        find(i, j+size/2, size/2);
        /* 3사분면 탐색 */
        find(i+size/2, j, size/2);
        /* 4사분면 탐색 */
        find(i+size/2,j+size/2, size/2);
    }else // 현재 사분면에 존재하지 않는다면 찾지않고 수만 더함
    {
        ans += size*size;
    }
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> r >> c;
    find(0, 0, (1<<N));
    return 0;
}

• 시간 초과 해결
  : 모든 사분면에 대해 find하지 않고, 검사해서 안에 없으면 해당 size*size만큼 더하기

• 로직
  1) 현재 좌표에 대해 size만큼의 사각형 범위 안에 r,c가 있는지 검사
  2-1) 있다면, size가 1이 될 때 까지 찾아 들어간다
  2-2) 없다면, 해당 구역은 건너 뛰어야 하므로 size*size만큼 ans에 더한다
  3) size가 1일 때 우리가 원하는 정답이 나오게 된다