[SWEA]#2117 [모의 SW 역량테스트] 홈 방범 서비스

문제

#2117 [모의 SW 역량테스트] 홈 방범 서비스

입력

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M이 주어진다.

그 다음 줄부터 N*N 크기의 도시정보가 주어진다. 지도에서 1은 집이 위치한 곳이고, 나머지는 0이다.

출력

테스트 케이스의 개수만큼 T줄에 T개의 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 "#x"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (x는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾았을 때,

그 때의 서비스를 제공 받는 집들의 수이다.

예제 입력 1

10
8 3
0 0 0 0 0 1 0 0
0 1 0 1 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 1 0 1 0 0
0 0 1 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 1 0
1 0 0 0 0 0 0 0
…

예제 출력 1

#1 5
#2 4
#3 24
#4 48
#5 3
#6 65
#7 22
#8 22
#9 78
#10 400

풀이

이 문제는 모든 경우의 수를 구하는 BruteForce 문제이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;

class Solution
{
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++)
        {
            String[] input = br.readLine().split(" ");
            int N = Integer.parseInt(input[0]);
            int M = Integer.parseInt(input[1]);
            HashMap<Integer, Pair> houses = new HashMap<>();
            int idx = 0;
            int max = -1;
            
            for(int i=0; i<N; i++) {
                input = br.readLine().split(" ");
                for(int j=0; j<N; j++) {
                    if(Integer.parseInt(input[j])==1) {
                        houses.put(idx, new Pair(i, j));
                        idx++;
                    }
                }
            }
            
            for(int x=0; x<N; x++) {
                for(int y=0; y<N; y++) {
                    for(int k=1; ; k++) {
                    	int K = cost(k);
                    	if(M*idx-K<0) break;
                    	int cnt = 0;
                    
                    	for(int j=0; j<idx; j++) {
                    		Pair p = houses.get(j);
                    		if(Math.abs(x-p.x)+Math.abs(y-p.y)<=k-1) cnt++;
                		}
                    	if(cnt*M-K>=0 && max<cnt)
                        	max = cnt;
                	}
                }   
            }
            
            System.out.println("#"+test_case+" "+max);
		}
	}
    
    public static class Pair {
        int x;
        int y;
        
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static int cost(int k) {
        if(k==1)	
            return 1;
        
        return (k-1)*4+cost(k-1);
    }
}