(JAVA) 2117. [모의 SW 역량테스트] 홈 방범 서비스

Standard

문제 링크: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

오랜만에 다시 풀다 보니 머리가 안 돌아가서 고생함.
– 홈 방범 영역을 계산하기 위해 k=1일 때 가운데를 0,0으로 해서 1군데 넣고, k=2일 때 -1,0 / 1,0 / 0,-1 / 0,1 4군데 넣고 (규칙이라면 마름모 꼴로 해서 x+y가 k-1인 모든 정수로 된 점을 넣는 식으로..) 이런 식으로 홈방범 영역 계산
– 처음에는 k=1부터 해서 늘려나가는 식으로 짰는데, 시간 초과가 나와서 로직 수정
– 처음에 map 만들 때 집 갯수를 세서, 집 갯수*비용이 운영 비용 (k-1 제곱+k 제곱)보다 작아지는 최초의 k를 구해서 k-1을 maxBound로 이용 (즉 이보다 큰 maxBound는 고려할 필요가 없음)
– k=maxBound부터 1씩 줄여나가면서 손해가 안나는 (>=0) 최초의 k가 나올 때까지 ‘서비스가 제공되는 집의 갯수’를 구함. 그랬더니 3초 기준으로 1.6초인가 해서 통과.

import java.io.*;
import java.util.*;

public class Solution {
	
	public static void main(String[] args) throws IOException {
		// System.setIn(new FileInputStream("./src/sample_input.txt"));
		
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
		
		try {
			int numCases = Integer.parseInt(reader.readLine());
	
			for (int i = 0; i < numCases; i++) {
				writer.write("#" + String.valueOf(i + 1) + " ");
				
				String[] tmp = reader.readLine().split(" ");
				int numN = Integer.parseInt(tmp[0]); // 도시 크기
				int numM = Integer.parseInt(tmp[1]); // 지불 비용
				
				// N, M 출력
				//writer.write(numN + " " + numM + System.lineSeparator());
				
				int[][] map = new int[numN][numN];
				int numAllHouse = 0;

				// 맵 생산
				for (int j = 0; j < numN; j++) {
					String[] tmp_ = reader.readLine().split(" ");
					
					for (int k = 0; k < tmp_.length; k++) {
						if (tmp_[k].equals("1")) {
							map[k][j] = 1;
							numAllHouse++;
						}
					}
				}
				
				List<String> serviceArea = new ArrayList<String>();
				
				int maxHouse = 0;
				
				// 서비스 영역 최대값 구하기
				int maxBound = 1;
				while(maxBound * maxBound + (maxBound - 1) * (maxBound - 1) < numAllHouse * numM) {
					maxBound++;
				}
				maxBound--; // while 문에서 탈출할 때는 이미 서비스 비용이 제공 수수료를 초과하므로, maxBound를 1 줄임 (서비스 비용이 제공 수수료보다 작은 최대값)
				
				while (true) {
					serviceArea.clear();
					
					// 서비스 영역 처리
					for (int j = 0; j < maxBound; j++) {
						if (j == 0)
							serviceArea.add("0/0");
						else {
							for (int k = 0; k <= j; k++) {
								int l = j - k;
								
								int tmp1 = k;
								int tmp2 = l;
								
								if (serviceArea.contains(tmp1 + "/" + tmp2) == false)
									serviceArea.add(tmp1 + "/" + tmp2);
								
								tmp1 = -k;
								tmp2 = l;
								
								if (serviceArea.contains(tmp1 + "/" + tmp2) == false)
									serviceArea.add(tmp1 + "/" + tmp2);
								
								tmp1 = k;
								tmp2 = -l;
								
								if (serviceArea.contains(tmp1 + "/" + tmp2) == false)
									serviceArea.add(tmp1 + "/" + tmp2);
								
								tmp1 = -k;
								tmp2 = -l;
								
								if (serviceArea.contains(tmp1 + "/" + tmp2) == false)
									serviceArea.add(tmp1 + "/" + tmp2);
							}
						}
					}
					
					// 실제 손익 계산 (하나씩 늘려가면서 해야되므로 loop 안에서 수행)
					int operationalCost = serviceArea.size();
					
					// k: 기준점 x, l: 기준점 y
					for (int k = 0; k <= numN - 1; k++) {
						for (int l = 0; l <= numN - 1; l++) { int count = 0; for (String entry: serviceArea) { String[] tmp__ = entry.split("/"); int x = k + Integer.parseInt(tmp__[0]); int y = l + Integer.parseInt(tmp__[1]); if (x >= 0 && x < numN && y >= 0 && y < numN) { if (map[x][y] == 1) count++; } } if (numM * count - operationalCost >= 0) { 
								if (maxHouse < count)
									maxHouse = count;								
							}
						}
					}
					
					if (maxHouse == 0) 
						maxBound--;
					else 
						break;
				}
				
				writer.write(maxHouse + System.lineSeparator());
				writer.flush();
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.