1074번-Z

중요 지식

---

이분탐색 - 문제 특성상 1/4씩 탐색 범위를 줄일 수 있는데 이 점은 탐색범위를 1/2씩 줄이는 이분탐색과 비슷하다

코드

---

#include <iostream>
#include <cmath>

using namespace std;


int main(){
    int N, r, c;
    int start = 0, mid, end;
    int row = 0, col = 0, rMid, cMid;

    cin >> N >> r >> c;

    for(;N >= 1; N--){
        end = (int)(pow(2, N-1) * pow(2, N-1));
        mid = (int)pow(2, N-1);
        rMid = row + mid;
        cMid = col + mid;
        
        if(r < rMid && c < cMid){
            start += end * 0;
        }else if(r < rMid && c >= cMid){
            start += end * 1;
            col += mid;
        }else if(r >= rMid && c < cMid){
            start += end * 2;  
            row += mid;          
        }else if(r >= rMid && c >= cMid){
            start += end * 3;
            row += mid;
            col += mid;
        }
    }
    
    cout << start;

    return 0;
}

풀이

---

이분탐색만 알면 쉽게 풀 수 있는 문제이다 

 

중요한 점

 1  Z모양으로 4칸을 탐색했기 때문에 방문 순서의 시작을 쉽게 알 수 있다

0번째 칸 =  (탐색할 배열의 크기의 0/4)

1번째 칸 =  (탐색할 배열의 크기의 1/4)

2번째 칸 =  (탐색할 배열의 크기의 2/4)

3번째 칸 =  (탐색할 배열의 크기의 3/4)

 

 2  이분탐색과 비슷하지만 행과 열을 따로 처리해줘야 한다 

2차원 배열인 행렬로 탐색하기 때문에 탐색 범위를 반으로 나눌 때 행은 행의 반, 열은 열의 반으로 따로 처리해야한다