[삼성 SW EA] 홈 방범 서비스

최대 K 범위는 NxN의 배열이 K에 다 들어갈 때 이다. 

마름모 모양의 방범 영역은 가운데에 1(K=1,2),3(K=3,4),5(K=5,6) 홀수의 정사각형을 가지므로, N이 홀수인 경우 최대 K의 범위는 N이다.

짝수인 경우, 최대 K는 N+2가 된다.

1~K까지의 방범 영역을 X,Y(1<=X<=N , 1<=Y<=N) 좌표에 두면서 이익이 날 수 있는 최소의 집이 있는지 검사하도록 하였다.

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
 
public class Solution {
   static int T,N,M, answer, operateFee,k;
   static int[][] maps;
   public static void main(String[] args) throws FileNotFoundException {
       Scanner sc = new Scanner(System.in);
      T = sc.nextInt();
      for(int tc=1;tc<=T;tc++){
         N = sc.nextInt();
         M = sc.nextInt();
         maps = new int[21][21];
         for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
               maps[i][j] = sc.nextInt();
            }
         }
         
         int maxHouseCount = 0;
         int maxCover = N%2==0 ? N+2 : N; // 운영 영역으로 커버할 수 있는 최대 크기
         
         k = 1; // 운영 영역의 크기
          while(k<=maxCover){
          
            operateFee = k*k + (k-1)*(k-1); // 운영비
            for(int i=1;i<=N;i++){
               for(int j=1;j<=N;j++){
                  int result = check(i,j);
                  if(result==-1)
                      continue;
                  maxHouseCount = Math.max(maxHouseCount, result);
               }
            }
            k++;
         }
                  
 
         System.out.println("#"+tc+" "+maxHouseCount);
      }
   }
   static int check(int x, int y) {
      int houseCount = 0;
      int minHouseCount = (operateFee%M==0) ? operateFee/M : operateFee/M+1; 
      
      for(int i=y-(k-1);i<=y;i++){
         for(int j=x-(k-(y-i+1));j<=x+(k-(y-i+1));j++){
               if(i<1 || j<1 || i>N || j>N)
               continue;
            if(maps[j][i]==1)
               houseCount++;
         }
      }
      
      for(int i=y+1;i<=y+(k-1);i++) {
          for(int j=x-((k-1)-(i-y));j<=x+((k-1)-(i-y));j++) {
              if(i<1 || j<1 || i>N || j>N)
                  continue;
               if(maps[j][i]==1)
                  houseCount++;
 
          }
      }
      
      if(houseCount < minHouseCount)
          return -1;
      
      return houseCount;
   }
 
}