2117 홈 방범 서비스

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu#none

서비스 영역의 운영 비용과 해당 영역 내의 집들을 통해 얻는 수익을 비교하여 손해 보지 않을 때 최대 집의 수를 구하는 문제이다. k를 넉넉잡아 1부터 최대 n+1까지 만들어서 서비스 영역의 중앙을 중심으로 해서 도시 전체를 스캔한다. count 함수는 해당 영역 안의 집의 수를 세는 함수이고 valid는 인덱스 범위를 검사하는 함수이다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int t,n,m,map[20][20],ans,cost[22];
 
bool vaild(int x,int y)
{
    return x>=0 && x<n && y>=0 && y<n;
}
 
int count(int x,int y,int k)
{
    int cnt=0;
    for(int i=x-k+1,l=1,s=y ; i<=x ; i++,l+=2,s--)
        for(int j=s;j<s+l;j++) if(vaild(i,j) && map[i][j]) cnt++;
    for(int i=x+k-1,l=1,s=y ; i>x ; i--,l+=2,s--)
        for(int j=s;j<s+l;j++) if(vaild(i,j) && map[i][j]) cnt++;
    return cnt;
}
 
void solve(int k)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            int cnt=count(i,j,k);
            if(cost[k]<=cnt*m)
                ans=max(ans,cnt);
        }
    }
}
 
int main()
{
    for(int i=1;i<=21;i++) cost[i]=i*i+(i-1)*(i-1);
    scanf("%d",&t);
    for(int T=1;T<=t;T++)
    {
        scanf("%d %d",&n,&m);
        for(int i=0;i<n;i++) for(int j=0;j<n;j++)
            scanf("%d",&map[i][j]);
        ans=0;
        for(int i=1;i<=n+1;i++)
            solve(i);
        printf("#%d %d\n",T,ans);
    }
    return 0;
}