[백준 1074 - C++] Z : 분할 정복

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

1074번: Z

문제

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

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

풀이

아 필기에 배경있는거 싫은데,, 굿노트가 업데이트 되면서 달라졌다...
처음엔 그냥 재귀만 하면 되는 간단한 문제구나~하고 재귀를 돌다가 구역 사이즈가 2*2가 됐을 때만 숫자들을 증가시키는 코드를 작성했다.
그랬더니 처참하게 시간초과!!!! (원래 쓴 코드에서 수정해서 필요 없는 조건도 들어가 있을 수 있음)
다시 생각을 해보니 (r, c)가 없는 구역은 굳이 잘라서 확인할 필요가 없다!!!!
N=15같은 입력에서 잘라서 다 확인을 하면 어마어마하게 시간이 오래 걸릴것이라는것을 예상할 수 있다.
그래서 그 구역에 대해서는 재귀를 호출하지말고 그냥 그 구역의 크기만 계산하는 값에 더해주면 된다.
재귀를 하면 난 시간복잡도가 너무 헷갈린다ㅠㅠ 반복문처럼 직관적이지가 않아서 그렇다는 핑계를 대본다!

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

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

int X[4] = {0, 0, 1, 1};
int Y[4] = {0, 1, 0, 1};

void sol (int now_n, int now_r, int now_c){
    if (now_n==1){
        if(now_r<=r && now_r+1 >= r && now_c <=c && now_c+1 >= c){
            for(int i=0; i<4; i++){
                if(r == now_r + X[i] && c== now_c+Y[i]){
                    printf("%d\n", result);
                    exit(0);
                }
                result++;
            }
        }
        else
            result+=4;
    }
    else{
        if(now_r<=r && now_c<=c && now_r+pow(2, now_n)>=r && now_c+pow(2, now_n)>=c){
            sol(now_n-1, now_r, now_c);
            sol(now_n-1, now_r, now_c+pow(2, now_n-1));
            sol(now_n-1, now_r+pow(2, now_n-1), now_c);
            sol(now_n-1, now_r+pow(2, now_n-1), now_c+pow(2, now_n-1));
        }
        else
            result+=pow(2, now_n)*pow(2, now_n);
    }
}

int main (void){
    
    scanf("%d %d %d", &n, &r, &c);
    
    sol(n, 0, 0);
}