swe 2115 벌꿀채취

- dfs + dfs - dfs 로 먼저 벌통의 영역을 선정한 후에 - 선정된 벌통에 대해서 dfs 를 통해서 최대 벌꿀량을 계산합니다. - dfs + dfs 둘다 풀으니 왕뿌듯합니당.

/*
2121 벌꿀 채취 시작
채취하여 얻을 수 있는 수익의 합이 최대.
40분 컷

중복 x, 조합입니다. 

1. 두 명의 벌의 선택한 영역. dfs (중복 x, 조합)
2. 선택된 곳에서 최대 양이 나올 수 있도록 계산하기.

2-1. 숫자를 합해서, 10이 넘어가지 안도록 하고, 그것들의 개별 곱을 저장해두기.
dfs 중복 x, 조합입니다.
*/
 
#include <iostream>
#include <algorithm>
using namespace std;
#define SIZE 11
 
int map[SIZE][SIZE];
int visit[SIZE][SIZE];
int ans;
int N, M, C;
int maxVal = 0;
int maxVal2 = 0;
int maxVal3 = 0;
int isFine;
int tong[2][5]; // 1 에는 하나, 2에도 하나씩 저장합니다. 통의 최대 크기는 5
int index;
 
void problemIn() {
    cin >> N >> M >> C;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
}
 
void init() {
    maxVal = maxVal2= maxVal3 =0;
}
 
/*
현재 tong[1] = { 7,2,9}
tong[2] = {6,6,6};

안의 숫자의 합이 10 이전이면, 제곱값을 저장합니다.
독립적으로 진행가능합니다. 먼저 통1에 대해서 진행합니다.
*/
 
void dfs2(int pos, int sum, int square) {
    if (pos == M) {
        maxVal = max(maxVal, square);
        return;
    }
    if (sum + tong[0][pos] <= C) {
        dfs2(pos + 1, sum + tong[0][pos], square + pow(tong[0][pos], 2));
    }
    dfs2(pos + 1, sum, square);
}
void dfs3(int pos, int sum, int square) {
    if (pos == M) {
        maxVal2 = max(maxVal2, square);
        return;
    }
    if (sum + tong[1][pos] <= C) {
        dfs3(pos + 1, sum + tong[1][pos], square + pow(tong[1][pos], 2));
    }
    dfs3(pos + 1, sum, square);
}
 
void check() {
    maxVal = maxVal2 = 0;
    dfs2(0, 0, 0);
    dfs3(0, 0, 0);
    maxVal3 = max(maxVal3, maxVal + maxVal2);
}
 
 
/*
벌통 선택 2개 하기,
중복을 최소화하기 위한 변수 startI
*/
void dfs(int depth, int startI) {
 
    if (depth == 2) {
        check();
        return;
    }
 
    for (int i = startI; i < N; i++) {
        for (int j = 0; j < (N - M + 1); j++) {
            // 중복 피하기.
            for (int l = 0; l < M; l++) {
                if (visit[i][j + l] == 0) {
                    isFine = 1;
                }
                else {
                    isFine = 0;
                    break;
                }
            }
            if (isFine) {
                index = 0;
                for (int k = 0; k < M; k++) {
                    visit[i][j + k] = 1;
                    tong[depth][index] = map[i][j + k];
                    index++;
                }
                dfs(depth + 1, startI);
                for (int k = 0; k < M; k++) {
                    visit[i][j + k] = 0;
                }
            }
        }
    }
}
 
void solve() {
    dfs(0, 0);
}
 
int main() {
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        problemIn();
        solve();
        cout << "#" << tc << " " << maxVal3 << endl;
        init();
    }
    return 0;
}