분할 정복

1074번: Z

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

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int Row, Col;
int Answer;

void Solve(int X, int Y, int N)
{
    if (X == Row && Y == Col)
    {
        cout << Answer << '\n';
        return;
    }

    // 검사하는 사분면에 속해 있다면.
    if (Row < X + N && Row >= X && Col < Y + N && Col >= Y)
    {
        Solve(X, Y, N / 2);
        Solve(X, Y + (N / 2), N / 2);
        Solve(X + (N / 2), Y, N / 2);
        Solve(X + (N / 2), Y + (N / 2), N / 2);
    }
    // 검사하는 사분면에 속해 있지 않다면.
    else Answer += (N * N);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); 
    //freopen("input.txt", "rt", stdin);

    int N;
    cin >> N >> Row >> Col;

    Solve(0, 0, (1 << N));

    return 0;
}

---

2630번: 색종이 만들기

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

1. Board[x][y]가 1(=파란색)일 때의 NumBlue를 체크한다.
2. NumBlue가 0이면(=전체 흰색) ++ResWhite, N * N개면(=전체 파란색) ++ResBlue
3. 둘 다 아니면, 분할한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;
int Board[129][129];
int ResWhite, ResBlue;

void Solve(int X, int Y, int N)
{
    int NumBlue{};
    for (int i = X; i < X + N; ++i)
    {
        for (int j = Y; j < Y + N; ++j)
        {
            if (1 == Board[i][j])
            {
                ++NumBlue;
            }
        }
    }

    if (NumBlue == 0)
    {
        ++ResWhite;
    }
    else if (NumBlue == N * N)
    {
        ++ResBlue;
    }
    else
    {
        Solve(X, Y, (N / 2));
        Solve(X + (N / 2), Y, (N / 2));
        Solve(X, Y + (N / 2), (N / 2));
        Solve(X + (N / 2), Y + (N / 2), (N / 2));
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); 
    //freopen("input.txt", "rt", stdin);

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            cin >> Board[i][j];
        }
    }

    Solve(0, 0, N);

    cout << ResWhite << endl << ResBlue;

    return 0;
}