[Java] 2117. 홈 방범 서비스

모의 SW 역량테스트 2117. 홈 방범 서비스

 

문제 출처:  https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

SW Expert Academy

Brute Force 하게 해결.

 

전체 소스코드 아래 추가적인 설명이 있습니다.

---

1. 전체 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Solution {

	static int N, M;
	static int[][] map;
	static int maxHouse;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());

		for (int test_case = 1; test_case <= T; test_case++) {
			StringTokenizer st = new StringTokenizer(br.readLine());

			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			map = new int[5 * N][5 * N];
			
			maxHouse = 1;
			int numOfHouse = 0;
			for (int i = 2 * N; i < 3 * N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 2 * N; j < 3 * N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if (map[i][j] == 1) {
						numOfHouse++;
					}
				}
			}

			if (numOfHouse == 1) {
				bw.append("#" + test_case + " 1\n");
				continue;
			}

			int maxProfit = M * numOfHouse;
			int k = 1;
			while (true) {
				if (computeCost(k + 1) <= maxProfit)
					k++;
				else
					break;
			}

			for (int kIdx = k; kIdx > 0; kIdx--) {
				for (int i = 2 * N; i < 3 * N; i++) {
					for (int j = 2 * N; j < 3 * N; j++) {
						setSecurityCorp(i, j, kIdx);
					}
				}
			}

			bw.append("#" + test_case + " "+maxHouse+"\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}

	private static void setSecurityCorp(int x, int y, int k) {
		int n = 0;
		int count = 0;
		for (int i = x - k + 1; i < x; i++) {
			for (int j = y - n; j <= y + n; j++) {
				if (map[i][j] == 1)
					count++;
			}
			n++;
		}

		for (int i = x; i < x + k; i++) {
			for (int j = y - n; j <= y + n; j++) {
				if (map[i][j] == 1)
					count++;
			}
			n--;
		}

		if (count * M >= computeCost(k)) {
			if (maxHouse < count) {
				maxHouse = count;				
			}
		}
	}

	private static int computeCost(int k) {
		return (2 * (k - 1) * k + 1);
	}
	
}

 

 

---

2. 풀이

 

Brute Force. 방범 소의 중심 좌표와 반경 k를 받으면 지도에서 해당 구역 내 존재하는 집의 수를 카운트하여 M만큼 곱하여 얻을 수 있는 수입을 계산하였다. 수입과 서비스 반경을 뺀 값이 0보다 크며 이때 제공할 수 있는 집의 개수가 최대 일시 최댓값을 갱신.

 

반경 k에 대해 발생하는 비용은 계차수열의 형태를 띄어 일반식으로 k에대해 비용을 계산하는 식을 만들어 사용해주었다.

 

private static int computeCost(int k) {
		return (2 * (k - 1) * k + 1);
}

 

방범 소의 범위를 지도에 적용하면서 필터링하는 과정에서 지도의 크기를 넘어가는 것에 대해 문제가 발생할 수 있다. 이를 위해 약간의 트릭을 추가하였다. 배열의 크기를 최대 지도 N * N을 담을 수 있는 크기([5 * N][5 * N])로 잡아 지도의 중심에 input으로 들어온 지도의 값을 넣어주었고, 더 큰 지도에서 필터링을 진행하여 인덱스로 인한 에러 처리 없이 카운트할 수 있었다.