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

문제

한수는 크기가 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

예제 입력 / 출력

입력
2 3 1

출력
11

코드

#include <iostream>
#include <cmath>
using namespace std;

int n,r,c;
int cnt = 0;
bool flag;

void rec(int size,int y, int x)
{
    if(size==1)
    {
        if(y == r && x == c)
           flag = true;  
        else
            cnt++;
        return;
    }     
    for(int i=y; i<y+size; i=i+(size/2))
    {
        for(int j=x; j<x+size; j=j+(size/2))
        {
            
            if(flag == true)
                return;
            
            if((i<=r && j<=c) && (r< i+size  && c < j+size)) //  0,4 , 3,7
            {
                rec(size/2,i,j);
            }
            else
                cnt += pow((size/2),2);
        }
    }
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> r >> c;
    int map_size;
    
    int num=0;

    map_size = pow(2,n);   
    rec(map_size,0,0);

    cout << cnt << '\n';
    return 0;
    
}

문제 해결

시간 제한이 0.5초이기 때문에 굉장히 빠듯한 문제였다. 처음엔 모든 구간을 재귀로 탐색하면서 카운트를 세는 방식으로 코드를 작성하였는데 시간 초과가 발생하였고 이로 인해 r,c로 조건을 걸어 탐색하지 않아도 되는 부분의 구간을 통째로 카운트 하는 방식으로 코드를 재작성하였다 재귀를 들어가는 구간을 나누는 코드와 구간을 통째로 더할 때 얼만큼 더해야 하는지를 생각하는 부분이 어려웠던 것 같다