백준 문제풀이 : (1074) Z - C/C++

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

1074번: Z

 

시간 제한	메모리 제한	난이도	알고리즘 분류
0.5초	512 MB	Silver1	분할정복, 재귀

 

 

문제

 

 

풀이

문제에서 주어진 예제를 들여다보면 z 모양을 그리며 이동하는 재귀적 패턴을 찾을 수 있다. 표의 한 변에 있는 숫자의 개수를 noc(NumOfCells)라고 했을 때, 문제는 noc*noc 개의 칸으로 이루어진 표를 균등하게 4분면으로 나눈 후, 2사분면 → 1사분면 → 3사분면 → 4사분면 순으로 방문하는 패턴을 반복한다. 이 패턴을 파악했을 때 가장 단순하게 떠올릴 수 있는 방법은, 크기가 noc*noc인 2차원 배열을 생성 후 규칙에 맞게 순서대로 숫자를 채워넣는 것이다. 이 방법을 사용하면 array[r][c]를 출력하여 간단하게 답을 구해낼 수 있다. 

 

하지만 이 방법을 사용할 경우 우리는 r과 c의 값과 무관하게 무조건 배열의 모든 수를 채워야만 답을 구해낼 수 있다. noc의 값이 작은 수라면 상관 없겠지만 문제에서 주어지는 noc의 최대값은 2의 15승인 32,768이다. 시간복잡도가 최소 noc의 2제곱이므로 0.5초만에 풀 수 없는 테스트 케이스가 존재한다.

 

따라서 훨씬 빠르게 풀 수 있는 방법을 생각해봐야한다. 

 

이 문제를 풀기 위한 두 가지 포인트가 있다. 첫번째는 배열을 사용하지 않고 r행 c열의 위치를 어떻게 찾아낼 것인가, 그리고 두 번째는 r행 c열의 위치에 어떤 숫자가 적혀있을 것인가이다. 

 

먼저 첫번째, r행 c열의 위치를 어떻게 찾아낼 것인가부터 따져보도록 하자. 문제에서 r행 c열에 해당하는 r과 c값이 주어졌으므로, 가상의 배열을 네 등분할 기준점(x,y)을 중심으로 r과 c의 값을 비교하여 어떤 사분면에 r행 c열이 위치해있는 지를 알아낼 수가 있다. (x, y)의 초기값은 (noc/2, noc/2)이 될 것이다.

 

x>=r && y>=c 일 경우에는 2사분면에,

x<r && y>=c 일 경우에는 3사분면에,

x>=r && y<c 일 경우에는 1사분면에,

x<r && y<c 일 경우에는 4사분면에 (r, c)의 값이 위치하게 된다.

 

*이 문제에서는 r값이 y축, c값이 x축에 대응됨에 주의하자.

 

매 재귀 시 마다 noc의 값은 1/2 비율로 줄어듦으로, 가장 하위 레벨 재귀에서는 각 사분면에 하나의 숫자만이 존재하게 되고 동일한 비교문을 거쳐 정답이 적힌 칸에 도달하게 된다. 각 재귀 마다 어떤 사분면으로 이동했는지에 따라 기준점의 위치도 달라진다.

 

2사분면으로 이동 → x값 감소, y값 감소

1사분면으로 이동 → x값 감소, y값 증가

3사분면으로 이동 → x값 증가, y값 감소

4사분면으로 이동 → x값 증가, y값 증가

 

증감값은 현재 noc의 1/4 이다. 이 방식으로 (r, c)의 위치를 탐색해나가면 이분 탐색과 동일한 시간 복잡도로 (r, c)의 위치(몇 사분면에 위치하는가)를 알아낼 수 있다. 

 

이제 (r,c)의 위치에 어떤 숫자가 적혀있는 지를 고려해보자. noc의 값이 8일 경우 가상의 배열에 적히는 수는 0부터 63까지가 된다. (noc*noc개의 숫자. 하지만 0부터 시작하므로 0 ~ noc*noc-1)

 

z 패턴이 반복되는 단위는 이 표를 4등분 한 것이므로 각 사분면에는 아래 범위의 수가 채워지게 된다.

 

2사분면 : 0 ~ 15  

1사분면 : 16 ~ 31

3사분면 : 32 ~ 47

4사분면 : 48 ~ 63

 

0부터 noc/4 개 씩 숫자를 채워넣게 되는 것이다. 그리고 재귀를 통해 반복할 때 마다, 어떤 사분면으로 이동하는지에 따라 탐색값이 규칙적으로 변한다. noc*noc의 값을 4로 나눈 값을 num이라고 하자.

 

(탐색값의 초기값 : 0)

2사분면으로 이동하는 경우 : 변함 없음

1사분면으로 이동하는 경우 : num 만큼 증가

3사분면으로 이동하는 경우 : num*2 만큼 증가

4사분면으로 이동하는 경우 : num*3 만큼 증가

 

문제에서 예시로 주어진 표를 보자. noc가 8인 이 표에서 (7, 5)에 위치한 수를 찾아본다고 하자. 

*표 인덱스가 (1,1)로 시작한다고 가정한다. 탐색값(count)의 초기값은 0이다.

 

첫번째 기준점은 noc를 2로 나눠 (4,4)이다. (7, 5)는 r과 c 모두 기준점보다 큰 수이므로 4사분면으로 이동한다.

탐색값 : +48을 하여 48이 됨.

 

두 번째 기준점은 (6,6)이 된다. (7, 5)는 r 값은 기준값보다 크지만, c값은 기준값보다 작으므로 3사분면으로 이동한다.

탐색값 : +8를 하여 56이 됨.

 

세 번째 기준점은 (7, 5)이 된다. (7,5)는 r 값이 기준값과 같거나 작고, c값도 기준값보다 작거나 같다. 따라서 1사분면으로 이동한다.

탐색값 : +0을 하여 56 그대로임.

 

네 번째에서는, 재귀 탈출 조건인 noc==1 에 걸려 현재 값인 56을 출력하고 탐색 종료한다.

 

 

코드 작성

#include <iostream>
#include <cmath>

using namespace std;
int result=0;

void draw (int noc, int count, int x, int y, int r, int c, int num) {
    if (noc==1) {
        result=count;
        return ;
    }
    
    if (x>=r && y>=c) { //2사분면
    //    printf("2로 이동 %d >= %d %d >= %d\n", x, r, y, c); 
        draw(noc/2, count, x-noc/4, y-noc/4, r, c, num/4); 
        
    }
    if (x<r && y>=c) { //3사분면
    //    printf("3로 이동 %d < %d %d >= %d\n", x, r, y, c); 
        draw(noc/2, count+num*2, x+noc/4, y-noc/4, r, c, num/4); 
        
    }
    if (x>=r && y<c) { //1사분면
    //    printf("1로 이동 %d >= %d %d < %d\n", x, r, y, c); 
        draw(noc/2, count+num, x-noc/4, y+noc/4, r, c, num/4); 
        
    } 
    if (x<r && y<c) { //4사분면
    //    printf("4로 이동 %d < %d %d < %d\n", x, r, y, c); 
        draw(noc/2, count+num*3, x+noc/4, y+noc/4, r, c, num/4); 
        
    }
}

int main() {
    int N, r, c;
    scanf("%d %d %d", &N, &r, &c);
    
    int noc = pow(2, N); //num of cell
    int count = 0, x=noc/2, y=noc/2;
    
    draw(noc, count, x, y, r+1, c+1, noc*noc/4);
    
    printf("%d", result);
    
}

 

 

 END.