[BOJ] 1074번 : Z

문제

한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음 그림은 N=3일 때의 예이다.

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

출처

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

알고리즘 분류

• 분할정복
• 재귀

접근 방법

최대 N이 15 가 될 수 있으므로, 직접 2차원 배열을 만들고 for문을 통해 순회하며 Numbering하는 것은 불가능하다. O(N^2)
문제를 자세히 보면 해당하는 r,c가 나올 때 까지, 사각형내에서 4조각으로 쪼개서 탐색하는 부분문제로 쪼갤 수 있다는 것을 알아차릴 수 있다.

이는 분할정복에서 큰 문제를 작은 문제들로 쪼개는 단계와 같다는 것을 알 수 있다.
더 이상 나눌 수 없는 작은 문제는 크기가 1인 사각형이 나왔을 때 이므로, 그런 조각이 나올 때 까지의 numbering을 해주면 되겠다.
( skip한 영역의 개수 * 해당 영역의 크기 만큼을 탐색이 완료 될 때 까지 더해주면 우리가 원하는 정답을 찾을 수 있다. )

분할 하는 방법은 큰 사각형의 가로를 반으로 나누는 부분 ~ 세로를 반으로 나누는 부분을 직선으로 그으면 + 모양으로 분할 되는데 한 변의 길이는 2의 K제곱 꼴의 형태이므로 분할 된 4개의 사각형의 길이는 모두 동일하다.

위 방법을 적용하면 subProblem에서도 루프불변성을 유지함을 알 수 있다.

소스 코드

#include <iostream>
#include <cmath>
using namespace std;
long long answer = 0 ;
int N,R,C;
void find(int n, int sy, int sx){
    if( n == 0 || ( sy == R && sx == C )){
        return ;
    }
    int size = pow(2,n-1);

    // 왼쪽 상단
    if( sy <= R && R < sy+size && sx <= C && C < sx + size ){
        find(n-1, sy, sx );
    }
    // 오른쪽 상단
    else if( sy <= R && R < sy+size && sx+size <= C && C < sx + 2*size ){
        answer += size*size;
        find( n-1, sy, sx+size );
    }
    // 왼쪽 하단
    else if( sy+size <= R && R < sy + 2*size && sx <= C && C < sx + size ){
        answer += 2*size*size;
        find( n-1, sy+size, sx );
    }
    // 오른쪽 하단
    else{
        answer += 3*size*size;
        find( n-1, sy+size, sx+size );
    }
    return;
}
int main(void){
    cin >> N >> R >> C;
    // 2차원 배열은 항상 2^N * 2^N의 모양

    // 재귀적으로 1개의 칸이 나올 때 까지 4분할을 한다.
    find(N,0,0);
    cout << answer ;
    return 0;
}