/<> 백준 1074번 : Z (C언어)

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

 

 

이 문제 속 2차원 배열의 특징은 사분면을 이루면서 정사각형 형태를 이룬다는 것입니다.

문제의 배열 이미지에 사분면을 구분해보겠습니다.

 

 N = 1인 경우 사분면을 나눈 모습

 

N = 2인 경우 사분면을 나눈 모습

 

N = 3인 경우 사분면을 나눈 모습

 

 

1. r행 c열의 위치가 배열에서 몇 사분면에 있는지 판단합니다.

 

2. 0을 초기값으로 설정하고, 몇 사분면인지와 배열의 크기에 따라 가중치를 더합니다.

 

3. 초기값에 가중치를더한 후 해당 사분면을 새로운 기준으로 1번째 과정과 2번째 과정을 반복합니다.

 

4. 가중치는 배열의 크기 N을 기준으로 4^(N-1)입니다(배열이 커지는 과정과 동일). 새로운 사분면으로 진행 시 r과 c의 크기도 사분면이 줄은 만큼 감소시킵니다.

 

5. 새로운 사분면의 크기가 2 X 2가 되면 마지막 연산을 진행합니다.

 

 

<코드>

#include <stdio.h>

int main() {
        int N, r, c;
        scanf("%d %d %d", &N, &r, &c);
        int pos = 0;
        float size = 1;
        int size2 = 1;
        for(int i = 0; i < N; i++) size *= 2;
        for(int i = 0; i < N - 1; i++) size2 *= 4;
        while(size > 1) {
                if(r < size / 2 && c >= size / 2) {
                        pos += size2;
                        c -= size / 2;
                } // 2 사분면
                else if(r >= size / 2 && c < size / 2) {
                        pos += size2 * 2;
                        r -= size / 2;
                } // 3 사분면
                else if(r >= size / 2 && c >= size / 2) {
                        pos += size2 * 3;
                        r -= size / 2;
                        c -= size / 2;
                } // 4 사분면
                size /= 2;
                size2 /= 4;
        }


        printf("%d\n", pos);
        return 0;
}

 

 

문제를 맨 처음 봤을 때 복잡한 그림에 거부감이 들었던 기억이 납니다 ㅋㅋㅋㅋ. 지금 와서 보니 꽤나 간단한...