[분할정복] 백준 1074 c++

Divide and conquer algorithm, 분할 정복 알고리즘

: 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법

• 보통 재귀함수를 통해 구현

function F(x):
  if F(x)의 문제가 간단 then:
    return F(x)을 직접 계산한 값
  else:
    x를 y1, y2로 분할
    F(y1)과 F(y2)를 호출
    return F(y1), F(y2)로부터 F(x)를 구한 값

 

어렵다..

 

처음에는 2차원 배열의 모든 칸을 돌면서 숫자를 써넣은 다음 r, c에 맞는 칸의 값을 출력하는 방법을 생각했는데 어떻게 코드를 작성해야 할 지 감이 잘 안 옴

---

• 제출 코드

#include <iostream>
#include <cmath>

using namespace std;

int **arr;
int r, c;
int n = 0;

void z(int x, int y, int sz)
{
    // r,c면 값 출력
    if(x == r && y == c)
    {
        cout << n << endl;
        return;
    }
        
    // 이번 칸에 있으면 탐색
    if(r < x+sz && c < y+sz && r >= x && c >= y)
    {
        z(x, y, sz/2);
        z(x, y+sz/2, sz/2);
        z(x+sz/2, y, sz/2);
        z(x+sz/2, y+sz/2, sz/2);
    }
    // 이번 칸에 없으면 다음 칸으로
    else
    {
        n += sz*sz;
    }
}

int main()
{
    int N;
    cin >> N >> r >> c;

    int size = pow(2,N);
    
    z(0, 0, size);

    return 0;
}

 

여러 블로그 참고했음 하 어렵다