[BOJ][C++] 백준 1074번: Z

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

1074번: Z

 

문제

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

풀이

 

#include <iostream>

using namespace std;

long long ans=0;

void z(int x, int y, int n){
    
    if(n == 0){
        return;
    }
    
    //2^n 구하기 (side)
    int side = 1;
    for(int i=0; i<n; i++){
        side *= 2;
    }
    int star = side/2 - 1;      //2^(n-1)-1 구하기 (사분면을 나누는 기준점)
    long long square = (side/2)*(side/2);  //2^(n-1) * 2^(n-1) 구하기 (한 사분면의 넓이)
        
    //사분면 판정 후 계산
    int new_x, new_y, new_n;
    
    if(x<=star && y<=star){
        new_x = x; new_y = y;
        ans += 0;
    }
    else if(x>star && y<=star){
        new_x = x-(star+1); new_y = y;
        ans += square;
    }
    else if(x <= star && y > star){
        new_x = x; new_y = y - (star+1);
        ans += 2 * square;
    }
    else if(x > star && y > star) {
        new_x = x-(star+1); new_y = y-(star+1);
        ans += 3 * square;
    }
    
    new_n = n--;

    z(new_x,new_y,n--);
}

int main() {
    int n, x, y;
    cin >> n >> y >> x;

    z(x,y,n);

    cout << ans;
    
    return 0;
}

 

TIL

함수를 반복문에 돌리는것과 재귀함수는 다르다.... ㅠㅠ