문제 URL:
https://www.acmicpc.net/problem/1074
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
위 문제는 크기가 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;
}