2115 벌꿀채취

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu

가로로 m개 놓을 수 있는 겹치지 않는 두개의 구역을 모두 만들어 본다. getProfit 함수를 이용하여 각 구역 내에서 채취할 수 있는 최대 수익을 구한다. 두개의 구역의 리턴값의 합 중에서 가장 큰 값이 정답이다.

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
 
int t,n,m,c,map[10][10],ans;
 
int getProfit(vector<int> &a)
{
    int MAX=0;
    for(int i=1;i<=m;i++)
    {
        vector<int> p(m,1);
        for(int j=0;j<i;j++) p[j]=0;
        do
        {
            int sqr=0,sum=0;
            for(int j=0;j<m;j++) if(p[j]==0)
                sqr+=a[j]*a[j],sum+=a[j];
            if(sum<=c) MAX=max(MAX,sqr);
        } while(next_permutation(p.begin(),p.end()));
    }
    return MAX;
}
 
void solve()
{
    vector<pair<int,int>> v; // 모든 경우의 수의 시작점
    for(int i=0;i<n;i++) for(int j=0;j<=n-m;j++)
        v.push_back({i,j});
 
    int size=v.size();
    for(int i=0;i<size;i++)
    {
        for(int j=i+1;j<size;j++)
        {
            int x1=v[i].first,y1=v[i].second;
            int x2=v[j].first,y2=v[j].second;
            if(x1==x2 && abs(y1-y2)<m) continue;
            vector<int> a(m),b(m);
            for(int k=0;k<m;k++)
            {
                a[k]=map[x1][y1+k];
                b[k]=map[x2][y2+k];
            }
            int total=getProfit(a)+getProfit(b);
            ans=max(ans,total);
        }
    }
}
 
int main()
{
    scanf("%d",&t);
    for(int T=1;T<=t;T++)
    {
        scanf("%d %d %d",&n,&m,&c);
        for(int i=0;i<n;i++) for(int j=0;j<n;j++)
            scanf("%d",&map[i][j]);
        ans=0;
        solve();
        printf("#%d %d\n",T,ans);
    }
    return 0;
}