[C++]1074번 Z

JongHyeon_Seo·2023년 3월 20일
0

문제

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

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

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

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

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

입력

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

출력

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

코드

#include <iostream>

using namespace std;

int row, col, cnt = -1;
int z(int l, int r, int c){
    if(l == 2){
        if(row > r || col > c){
            cnt += 4;
            return -1;
        }
        for(int i = 1; i >= 0; i--){
            for(int j = 1; j >= 0; j--){
                cnt++;
                if((r - i == row) && (c - j == col)) return cnt;
            }
        }
        return -1;
    }
    else{
        int ans, tr, tc;
        for(int i = 1; i >= 0; i--){
            for(int j = 1; j >= 0; j--){
                tr = r - ((l / 2) * i);
                tc = c - ((l / 2) * j);
                if(row > tr || col > tc) cnt += (l / 2) * (l / 2);
                else{
                    ans = z(l / 2, tr, tc);
                    if(ans != -1) return ans;
                }
            }
        }
        return -1;
    }
}

int main(){
    int N, n = 1;
    cin >> N >> row >> col;
    for(int i = 0; i < N; i++) n *= 2;
    cout << z(n, n - 1, n - 1);
}

찾으려는 좌표가 어느 사분면에 있는지 확인할 수 있기 때문에 조건을 주어 시간을 줄일 수 있다

profile
코딩 코딩

0개의 댓글