<Baekjoon> Z#1074

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

무엇을 구하는 문제인가?

n이 주어졌을 때, 2^n * 2^n의 정사각형에서 4등분 후 문제에서 주어진 순서대로 탐색할 때, (r, c)는 몇번째로 나오는지 구하는 문제이다.

​

해결 전략

4등분으로 분할하여, 문제에서 주어진 순서대로 호출하면 되는 간단한 문제이다.

4등분하여, r, c가 포함될 때만 호출하여 주었다.

​

알고리즘

1. n, r, c를 입력받는다.

2. Divde(초기 x, 초기 y, 길이)를 (0, 0, 2^n)을 초기값으로 함수를 호출하여준다.

3. 함수내에서 4등분 후 문제의 조건대로 차례로 호출하여준다.

4. x좌표, y좌표가 같다면 ans에 지금의 번지수를 넣어준다.

5. ans 출력

​

※주의 할점

전체탐색을 해서는 안된다.  r, c가 포함될 때만 호출하여 탐색해주어야 한다.

n범위가 2^15까지 올라가기에 2차원배열을 써 저장하는 방법은 안된다.

 

<소스코드>

#include <stdio.h>

int n, r, c;
int ans, ch;
int cnt = 0;

void Devide(int x, int y, int l)
{
    if (x == r && y == c) {
        ans = cnt;
        return;
    }
    if (r < x + l && r >= x && c < y + l && c >= y) {
        Devide(x, y, l / 2);
        Devide(x, y + (l / 2), l / 2);
        Devide(x + (l / 2), y, l / 2);
        Devide(x + (l / 2), y + (l / 2), l / 2);
    }
    else {
        cnt += l * l;
    }
}

int main()
{
    int i, j;
    scanf("%d %d %d", &n, &r, &c);
    Devide(0, 0, (1 << n));
    printf("%d", ans);
    return 0;
}

간단한 문젠줄 알고 막제출했는데....