2115 벌꿀채취

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
 
using namespace std;
 
int w_total, w_part, cap_max=10;
int box[15][15];
int rst_max;
int rst_pair_max;
int cur_cap;
 
void dfs(int y, int x, int depth);
int max_pair(vector<int> v);
void pair_dfs(int idx, int cur_pow,vector<int> v);
 
int main() {
    int t;
    scanf("%d", &t);
 
    for (int test = 1; test <= t; test++) {
        scanf("%d %d %d", &w_total, &w_part, &cap_max);
        memset(box, 0, sizeof(box));
        rst_max = -1;
 
        for (int i = 1; i <= w_total; i++) 
            for (int j = 1; j <= w_total; j++) 
                scanf("%d", &box[i][j]);
            
        for (int i = 1; i < w_total; i++) 
            for (int j = 1; j <= w_total - w_part + 1; j++) {
                for (int k = j; k < j + w_part; k++)
                    box[i][k] = -box[i][k];
                dfs(i, j, 1);
                for (int k = j; k <= j + w_part - 1; k++)
                    box[i][k] = -box[i][k];
            }
        
        printf("#%d %d\n", test, rst_max);
    }
}
 
void dfs(int y, int x, int depth) {
    if (depth == 1) {
        for (int i = y; i <= w_total; i++) 
            for (int j = 1; j <= w_total - w_part + 1; j++) {
                if ((i == y) && (j < x + w_part))
                    continue;
                
                for (int k = j; k < j + w_part; k++)
                    box[i][k] = -box[i][k];
                dfs(i, j, 2);
                for (int k = j; k < j + w_part; k++)
                    box[i][k] = -box[i][k];
            }        
    }
    else {
        int total_honey = 0;
        for (int i = 1; i <= w_total; i++) 
            for (int j = 1; j <= w_total; j++) 
                if ((box[i][j] < 0) && (box[i][j + w_part - 1] < 0)) {        
                    // 연달아 이어져 있는 경우엔 제외한다**************
                    if (!((box[i][j - 1] >= 0) || (box[i][j + w_part] >= 0)))
                        continue;
 
                    // 총량을 넘는지 확인하기 위함***************
                    int tmp = 0;
                    vector<int> tmp_vec;
                    for (int k = j; k < j + w_part; k++) {
                        tmp += (-box[i][k]);
                        tmp_vec.push_back(-box[i][k]);
                    }
                    
                    if (tmp <= cap_max) // 총량을 넘지 않는 경우
                        for (int z = 0; z < tmp_vec.size(); z++)
                            total_honey += pow(tmp_vec[z], 2);                    
                    else     // 총량을 초과해서, 최적의 값을 찾아야 하는 경우
                        total_honey += (max_pair(tmp_vec));                            
                }        
        
        if (rst_max < total_honey)
            rst_max = total_honey;
    }
}
 
int max_pair(vector<int> v) {
    rst_pair_max = -1;
    
    for (int i = 0; i < v.size(); i++) {
        cur_cap = v[i];
        pair_dfs(i, pow(cur_cap, 2), v);
        cur_cap = 0;
    }
    return rst_pair_max;
}
 
void pair_dfs(int idx, int cur_pow, vector<int> v) {
    if (cur_cap > cap_max) {
        cur_pow -= pow(v[idx], 2);
 
        if (cur_pow > rst_pair_max)
            rst_pair_max = cur_pow;
    }
    else if (idx >= v.size() - 1) 
        if (cur_pow > rst_pair_max)
            rst_pair_max = cur_pow;
    else 
        for (int i = idx + 1; i < v.size(); i++) {
            cur_cap += v[i];
            pair_dfs(i, cur_pow + pow(v[i], 2), v);
            cur_cap -= v[i];
        }
}

쉽다고 생각했는데, 막상 쉽진 않았다

이중 dfs문이 필요한 문제였다.

소요시간은 아마 2시간 이내였을거같다.