[BOJ] 1074번 : Z

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

1074번: Z

 

divide and conquer 문제인데, 다소 까다로운 부분이 있다. 직접 2차원 배열을 돌면서 수를 일일이 입력하고 다니면 N>=15라는 조건 때문에 시간 초과가 발생한다. 따라서 4개의 사분면으로 분할하여 계산을 생략해주는 과정이 반드시 필요하다. 나는 sizeRec에 미리 작은 사분면의 넓이를 저장한 후에 어느쪽 사분면이냐에 따라서 0, 1, 2, 3을 곱해 주어 직접 계산하는 과정을 생략하였다.

 

또 한 가지 유의하여야 할 점은 행과 열의 시작점이 0인지, 1인지 명시하고 있지 않지만 0에서 시작하는 것으로 생각한다는 점, 숫자를 세는 것의 시작 역시도 1에서 시작하는 것이 아닌 0에서 시작하여야 한다는 점이다. 이 점을 간과했다가 잠시 당황하였다.

 

시간 복잡도는 각 subproblem에서 특별히 반복문 등을 사용하지 않으므로 subproblem의 차수인 O(N)이 된다.

 

 

#include <stdio.h>
 
int n, r, c; 
 
int pow(int x, int y) {
    int sum = 1;
    for(int i = 0; i < y; i++) {
        sum *= x;
    }
    return sum;
}
 
int numCount(int left, int right, int up, int down) {
    
    int wmid = (left+right)/2;
    int hmid = (up+down)/2;
    int sizeRec = pow(wmid-left+1,2);
    
    if(left == right && up == down) return 0;
    
    if(c <= wmid && r <= hmid) {
        return numCount(left, wmid, up, hmid);
    }
    else if(c > wmid && r <= hmid) {
        return numCount(wmid+1, right, up, hmid) + sizeRec;
    }
    else if(c <= wmid && r > hmid) {
        return numCount(left, wmid, hmid+1, down) + (sizeRec*2);
    }
    else { //(c > wmid && r > hmid)
        return numCount(wmid+1, right, hmid+1, down) +(sizeRec*3);
    }
    
    
}
 
int main ( void ) {
    
    scanf("%d %d %d", &n, &r, &c);
    r+=1; c+=1;
    printf("%d\n", numCount(1,pow(2,n),1,pow(2,n)));
    
}