[백준 1074] Z C++

분할정복은 어려워!

 

코드만 보면 되게 간단해 보이는데 간단하게 만들기 위해 머리를 짜내는게 힘들다..

내 머리는 재귀적인 생각을 잘 못하는듯 하다

 

처음에 입력받은 N값을 2로 나눈 값을 solve()로 넘겨준다 -> 이 때 n == 2라고 가정하자(N == 3인 경우)

(r, c)가 몇 사분면에 있는지 4개의 if문을 통해서 판별한다

판별기준 : row + n 과 col + n

row+n을 기준으로 r이 이 값보다 작으면 1, 2 사분면 중 하나, 같거나 크면 3, 4 사분면 중 하나이다. 

col+n을 기준으로는 c가 이 값보다 작으면 1, 3 사분면 중 하나, 같거나 크면 2, 4 사분면 중 하나이다. 

총 4가지 기준으로 분할 정복을 실행하고 r, c의 위치를 찾으면 (n == 0) 리턴하여 지금까지 구한 result값을 출력한다

result값은 분할 될 때 r, c가 어느 사분면에 위치하는지에 따라 더해지는 값이 달라진다

#include <iostream>
#include <cmath>
using namespace std;
 
int N, r, c, result = 0;
 
void solve(int n, int row, int col){
    if(n == 0){
        return;
    }
    //1사분면
    if(row + n > r && col + n > c){
        solve(n/2, row, col);
    }
    //2사분면
    else if(row + n > r && col + n <= c){
        result = result + pow(n, 2);
        solve(n/2, row, col + n);
    }
    //3사분면
    else if(row + n <= r && col + n > c){
        result = result + 2*pow(n, 2);
        solve(n/2, row + n, col);
    }
    //4사분면
    else if(row + n <= r &&col + n <= c){
        result = result + 3*pow(n, 2);
        solve(n/2, row + n, col + n);
    }
 
}
 
int main(){
    cin >> N >> r >> c;
    solve(pow(2, N-1), 0, 0);
    cout << result << endl;
 
    return 0;
}
 

2021/01/03 0ms