백준 1074 Z C언어

 

 

#include <stdio.h>

int main(){

    int a;
    scanf("%d", &a);

    int n = 2;

    for(int i = 1; i < a; i++)
        n *= 2;

    int y, x;
    scanf("%d", &y);
    scanf("%d", &x);

    int answer = 0;
    while(n >= 1){
        if (y >= n/2 && x >= n/2)
            answer += n*n - (n/2)*(n/2);
        else if (y >= n/2 && x < n/2)
            answer += n*n - 2*(n/2)*(n/2);
        else if (y < n/2 && x >= n/2)
            answer += n*n - 3*(n/2)*(n/2);
        else if (y < n/2 && x < n/2)
            answer += n*n - 4*(n/2)*(n/2);
        if (n == 1)
            break;
        y = y % (n/2);
        x = x % (n/2);
        n /= 2;
    }
    printf("%d", answer - 1);


}

간만에 C로 풀었다.

이거 어렵다.

발상이 정말 어렵다. 5시간 걸렸다.

핵심은 '분할'이다. 가장 큰 사각형부터 2X2 사각형까지 Z자로 연산이 계속된다는 점을 파악한 후,

사각형을 계속 4등분 하면서 적절한 연산을 해주면 되는데,

2차원 배열의 인덱스가 n/2의 값을 가지는 4등분 된 사각형 안에서 다시 어떤 인덱스를 가지는 지 생각하는 게 정말 어려웠다.

해답은 나머지 연산.

좌표에 대해서 n으로 나머지 연산을 시행하면

사각형을 분할했을 때 그 사각형을 기준으로 상대적인 좌표의 위치를 알 수 있다.