[백준] 1074 Z(C++)

 

문제 URL: 

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

1074번: Z

위 문제는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색할 때 r행 c열을 몇 번째로 방문했는지 출력하는 문제로 분할 정복과 재귀를 이용하는 문제이다.

 

문제를 풀기 위해 가장 먼저 한 일은 r과 c에 따라 4등분으로 영역을 나누는 일이었다. 한 영역은 전체의 1/4이기 때문에 어떤 영역에 r과 c가 위치한다면 그 영역의 이전 영역 칸 수들을 정답 ans에 모두 더해주었다. 그 뒤 새로운 한 변(=기존 변을 반으로 나눈 값)과 r, c를 이용하여 위 작업을 진행하는 함수를 다시 호출해 주었다.  

---

#include <iostream>
#include <math.h>
using namespace std;

int n, r, c;
int ans = 0;

void recall(int side, int row, int col){
  int new_side = side/2;
  
  if(new_side > row && new_side > col){}
  else if(new_side > row && new_side <= col){
    ans += pow(new_side,2);
    col -= new_side;
  }else if(new_side <= row && new_side > col){
    ans += pow(new_side,2)*2;
    row -= new_side;
  }else{
    ans += pow(new_side,2)*3;
    row -= new_side;
    col -= new_side;
  }

  if(new_side == 1)
    return;
  else{
    recall(new_side, row, col);
  }
}


int main(){
  cin >> n >> r >> c;
  int side = pow(2, n);
  recall(side, r, c);

  cout << ans;
  return 0;
}