[C++] 백준 1074번 Z

문제

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

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

입력

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

출력

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

풀이

Z 모양으로 숫자가 증가하므로 방문할 위치가 4등분한 사각형의 어느지점에 있는지 찾고 그 전 사각형 만큼의 수를 더해주면 된다. 만약 4사분면에 있다면 1,2,3 사분면의 크기만큼 더해주는 식으로 말이다. 이를 재귀적으로 반복하면 문제를 해결할 수 있다.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int cnt=0;
bool tf=false;
int r,c;

void solve(int x, int y, int n){
  if (n==0) return;

  if (x <= r && r < x+n/2 && y <= c && c <y+n/2){
    solve(x,y,n/2);
  }
  if (x <= r && r < x+n/2 && y+n/2 <= c){
    cnt += n*n/4;
    solve(x,y+n/2,n/2);    
  }
  if (x+n/2 <= r && y <= c && c < y+n/2){
    cnt += n*n/2;
    solve(x+n/2,y,n/2);
  }
  if (x+n/2 <= r && y+n/2 <= c) {
    cnt += n*n/4*3;
    solve(x+n/2,y+n/2,n/2);
  }
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  int n;

  cin >> n >> r >> c;

  n = pow(2,n);

  solve(0,0,n);

  cout << cnt;
}