[BOJ] 1074 Z

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

1074번: Z

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

recursive-function

 

---------------------------------------------------풀이----------------------------------------------------

 

차례대로 왼쪽 위->오른쪽 위->왼쪽 아래->오른쪽 아래 를 방문한다.

따라서, 현재 보려는 사각형의 시작 행과 열(row_s, row_e), 끝나는 행과 열(col_s, col_e), 현재 사각형의 시작 숫자(num)을 인자로 넘겨준다.

이 사각형을 다시 네 구역으로 잘라 찾고자 하는 행과 열(row, col)을 포함하는 사각형의 부분으로 이동하는 것을 반복한다.

시작 행과 열이 찾는 행과 열과 일치하면 그 때의 시작 숫자인 num을 리턴하는 방식이다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>

using namespace std;

// 행과 열의 시작과 끝, 현재 시작할 숫자, 찾고있는 행과 열
int visit(int row_s, int row_e, int col_s, int col_e, int num, int row, int col){
    // 찾고있는 행, 열까지 도달한 경우
    if(row_s == row && col_s == col){
        return num;
    }
    int n = (row_e - row_s + 1)/2;  // 한 번 더 자를 경우의 한 변의 크기
    int size = n*n;
    // 왼쪽 위
    if(row_s <= row && row < row_s+n && col_s <= col && col < col_s+n){
        return visit(row_s, row_s+n-1, col_s, col_s+n-1, num, row, col);
    }
    // 오른쪽 위
    else if(row_s <= row && row < row_s+n && col_s+n <= col && col <= col_e){
        return visit(row_s, row_s+n-1, col_s+n, col_e, num+size, row, col);
    }
    // 왼쪽 아래
    else if(row_s+n <= row && row <= row_e && col_s <= col && col < col_s+n){
        return visit(row_s+n, row_e, col_s, col_s+n-1, num+size*2, row, col);
    }
    // 오른쪽 아래
    else{
        return visit(row_s+n, row_e, col_s+n, col_e, num+size*3, row, col);
    }
}

int main(void){
    FASTIO;
    int N, r, c;
    cin >> N >> r >> c;
    cout << visit(0, pow(2, N)-1, 0, pow(2, N)-1, 0, r, c) << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

재귀함수를 사용해보는 유형.