티스토리 뷰

알고리즘/BOJ

BOJ 1074, Z

아테즈 2019. 3. 25. 20:41

문제

한수는 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보다 작거나 같은 정수이다

출력

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




전형적인 프랙탈도형 문제이다.


큰 칸부터, 차례로 아래처럼



0 1 2 3순으로 방문할 것이므로, 방문 위치(순서)를 계산해주고 3번째 칸에 있다면 (2^n-1)^2 * 3


그 다음, 넓이가 4분의 1인 사각형에 대해서도 4등분해서 방문 위치를 잡아준다.


결국, 2 by 2 칸이 나올 때 까지 재귀적으로 해결해주면 끝!


아래 code의 mapsize[..]은 2^n을 빠르게 계산하기 위해 추가해 준 것이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <iostream>
 
using namespace std;
 
typedef long long LL;
 
int mapsize[16= { 1 };
 
int Z(intintint);
 
int main() {
    int N, R, C;
    for (int i = 1; i < 16; i++) {
        mapsize[i] = mapsize[i - 1* 2;
    }
 
    while (scanf("%d %d %d"&N, &R, &C) > 0) {
        printf("%d\n", Z(N, R, C) - 1);
    }
}
 
int Z(int n, int r, int c) {
    if (n == 0return 1;
 
    if (r < mapsize[n - 1]) {
        if (c < mapsize[n - 1]) return Z(n - 1, r, c);
        else return mapsize[n - 1* mapsize[n - 1+ Z(n - 1, r, c - mapsize[n - 1]);
    }
    else {
        if (c < mapsize[n - 1]) return mapsize[n - 1* mapsize[n - 1* 2 + Z(n - 1, r - mapsize[n - 1], c);
        else return mapsize[n - 1* mapsize[n - 1* 3 + Z(n - 1, r - mapsize[n - 1], c - mapsize[n - 1]);
    }
}
cs


'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 14956, Philosopher’s Walk  (0) 2019.03.25
BOJ 1074, Z  (0) 2019.03.25
BOJ 1049, 기타줄  (0) 2019.03.25
BOJ 1541, 잃어버린 괄호  (0) 2019.03.25
BOJ 1931, 회의실 배정  (0) 2019.03.25
BOJ 11399, ATM  (0) 2019.03.25
댓글
댓글쓰기 폼
공지사항
Total
21,753
Today
0
Yesterday
15
링크
TAG
more
«   2022/08   »
  1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31      
글 보관함