[1074] Z

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

1074 - Z

본문

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

$N > 1$인 경우, 배열을 크기가 $2^{N-1} \times 2^{N-1}$로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

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

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

입력

첫째 줄에 정수 $N, r, c$가 주어진다.

출력

$r$행 $c$열을 몇 번째로 방문했는지 출력한다.

제한

• $1 \leq N \leq 15$
• $0 \leq r, c < 2^N$

시간 제한	메모리 제한
0.5sec	512MB

---

풀이

진짜 간단한 문제다. 내가 구현하려는 목적이 무엇인지 확인하고 그대로 구현해내도록 노력해보자.

문제의 내용 자체가 재귀함수를 써달라고 이야기하고 있다. $2^N \times 2^N$ 크기의 배열을 4등분하여 생각하도록만 구현하면 나머지는 프로그램이 알아서 계산해줄 것이다. 칸의 개수를 세는 방법만 잘 정해주면 풀리는 문제.

일단 $N$이 주어졌다면, 배열은 총 $2^{2^N} = 4^N$칸이 존재한다. 그 중 찾으려는 칸이 어떤 범위에 존재하는지 확인하면 된다. 총 4가지 경우가 있다.

• $[0, \frac{1}{4}]$ 범위 : 1분면
• $[\frac{1}{4}, \frac{1}{2}]$ 범위 : 2분면
• $[\frac{1}{2}, \frac{3}{4}]$ 범위 : 3분면
• $[\frac{3}{4}, 1]$ 범위 : 4분면

분면 순서대로 움직이기 때문에 탐색된 칸의 개수를 셀 때 편해진다. 만약 내가 찾으려는 칸이 3분면에 소속된 칸이라면 1분면과 2분면의 칸들은 모두 탐색한 뒤에 진행될 것이므로, 2개의 분면에 존재하는 칸보다는 늦게 탐색될 것이고, 방문 순번은 최소 2개 분면의 칸의 수를 더한 값보다는 클 것이다. 이 방식으로 가장 큰 배열에서부터 탐색 범위를 줄여나가는 과정을 진행하면 답을 얻을 수 있다.

각 분면에 속해있는지 결정하는 방법은 $r$과 $c$가 특정 범위에 속해있는지 확인하면 된다. $r$이 현재 탐색하는 크기 $2^N$의 절반보다 크다면 아랫쪽, 아니라면 윗쪽일 것이다. 마찬가지로 $c$가 $2^N$의 절반보다 크다면 오른쪽, 아니라면 왼쪽이 될 것이다. 위 조건을 통해 $r$행 $c$열이 어떠한 범위에 속하는지 확인하면 된다.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2024 / 9 / 9

#include <stdio.h>

int main() {
    int n, r, c;
    scanf("%d %d %d", &n, &r, &c);
    int result = 0;

    for (; n > 0; --n) {
        int x = 0;

        if (r >= (1 << (n - 1))) {
            x += 2;
            r -= (1 << (n - 1));
        }
        if (c >= (1 << (n - 1))) {
            x += 1;
            c -= (1 << (n - 1));
        }

        result += (x * (1 << (2 * n - 2)));
    }

    printf("%d", result);
    return 0;
}