[1일 1알고] S1 31455 쿠키 자르기

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

 

전형적인 divide and conquer 문제입니다. 2차원 배열을 4개의 구역으로 나누고 이를 반복합니다.

 

제외되는 구역을 찾기위해서는 미리 합을 구해야하는데, 이것은 백트래킹으로 구할 수 없어보여 미리 합을 구해야했습니다.

 

아쉬운 측면이 있지만 다른 방법이 떠오르지 않네요.

누적합으로도 해보았지만 해당 문제에서는 오히려 조금 느렸습니다.

---

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>

using namespace std;
vector<vector<int>> v;
long long result = 0;
void dnc(int N, int r, int c, int sum);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    ostringstream oss;
    for (int t = 0; t < T; ++t)
    {
        int N;
        cin >> N;
        v = vector<vector<int>> (N, vector<int>(N, 0));
        result = 0;
        int sum = 0;
        for (int i = 0; i < N; ++i)
        {
            string s;
            cin >> s;
            for (int j = 0; j < N; ++j)
            {
                v[i][j] = s[j] - '0';
                sum += v[i][j];
            } 
        }
        dnc(N, 0, 0, sum);
        oss << result << '\n';
    }
    cout << oss.str();
    return 0;
}

void dnc(int N, int r, int c, int sum)
{
    int remain = sum % 4;
    int dr[4] = {r, r, r+N/2, r + N / 2 };
    int dc[4] = {c, c+N/2, c, c+N/2 };
    if (N/2 == 1)
    {
        for (int i = 0; i < 4; ++i)
        {
            if (i != remain)
            {
                result += v[dr[i]][dc[i]];
            }
        }
        return;
    }

    for (int i = 0; i < 4; ++i)
    {
        if (i != remain)
        {
            int nr = dr[i];
            int nc = dc[i];
            int sum = 0;
            for (int j = nr; j < nr + N / 2; ++j)
            {
                for (int k = nc; k < nc + N / 2; ++k)
                {
                    sum += v[j][k];
                }
            }
            dnc(N / 2, nr, nc, sum);
        }
    }
}