백준 1074번, z

백준 1074번 c++ 문제풀이

문제:

백준 1074

풀이:

1. 총 4분면으로 나누어서 진행한다.
2. 크기가 1*1이 될때까지 사각형을 4분면으로 쪼갠다(재귀함수를 통해 진행한다)
3. 1*1의 좌표가 찾는 좌표라면 그 값을 출력한다. 아니라면 방문한 순서를 증가시켜준다.
4. 위에 과정만 진행하면 시간 초과가 된다.
5. 4분면 중 찾는 좌표가 있는 분면만 재귀함수를 실행한다.(범위를 조건문으로 달아준다.)
6. 방문하지 않는 분면이 있다면, 방문한 순서는 그 분면의 크기를 더해주기만 하면 된다.

코드:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int input = 0;

void divide(long long n, long long a, long long b, long long r, long long k){//n, 시작 좌표 위치(x,y), 찾는 좌표(x,y)
    if(n >= 1){
        long long c= pow(2,n)/2;
        if(a+2*c>r && b+2*c>k && r>=a && k>=b){//현재 찾는 좌표가 이 사각형 안에 있다면,
            divide(n-1, a, b, r, k);//1사분면
            divide(n-1, a, b+c, r, k);//2사분면
            divide(n-1, a+c, b, r, k);//3사분면                        
            divide(n-1, a+c, b+c, r, k);//4사분면
        }
        else{//없다면 그냥 사각형 크기 만큼 증가
            input+=4*pow(c,2);
        }
    }else{//n=0일때, 즉 최대로 쪼개졋을 때, 한분면이 숫자 하나일때 
        if(a==r && b==k){
            cout << input;
        }
        input++;
    }
}

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

    long long n, r, c;

    cin >> n >> r >> c;

    long long s = pow(2,n);
    
    divide(n, 0, 0, r, c);

    return 0;
}

처음에는 무조건적으로 벡터에 저장하는 식으로 접근을 하다보니, 메모리 초과가 되었다. 하지만 막상 코드를 다시보니
벡터를 다 지우더라도 코드에 오류가 나지 않고 원하는 답도 제대로 출력된다는 것을 알게 되었다.

감사합니다.