[SWEA/모의 SW역량테스트] 2117. 홈 방범 서비스 - JAVA 자바

• 구현

길이가 K인 마름모 모양의 영역 내에 존재하는 집들이 있을 때, (운영비용) - (집이 지불하는 비용) * (집의 수) 가 양수이면서 집의 수가 최대일 때를 찾으면 된다.

 

K는 1부터 전체 영역을 포함할 수 있는 길이인 N * 2 까지 가능하며 K 길이와 좌표에따라 완전탐색으로 해결할 수 있는 문제이다. 로직은 생각하기 쉬우나 마름모 모양의 영역 내에 집이 존재하는가에 대한 체크하는 과정에서 어려움이 있었다.

마름모의 중심을 기준으로 반지름이 k인 원을 생각해주면 된다. 즉, 중심 좌표와 집의 좌표까지 거리가 k보다 작으면 마름모 영역 내에 존재한다는 것을 의미한다.

Math.abs(house[0] - i) + Math.abs(house[1] - j) < k

 

마름모 시렁

 

# 소스코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Solution {
    static int result;
    static boolean[][] board;
    static int n, m;

    public static void main(String[] args) throws NumberFormatException, IOException {
        // System.setIn(new FileInputStream("sample_input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        List<int[]> list = new ArrayList<>();
        int T = Integer.parseInt(br.readLine());

        for (int t = 1; t <= T; t++) {
            list.clear();
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            board = new boolean[n][n];

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    if (Integer.parseInt(st.nextToken()) == 1) list.add(new int[]{i, j});
                }
            }

            int count = 0;
            int max = 0;

            for (int k = 1; k <= n + 2; k++) {
                // 운영비용 구하기
                int work = k * k + (k - 1) * (k - 1);

                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        count = 0;

                        for (int l = 0; l < list.size(); l++) {
                            int[] house = list.get(l);

                                if (Math.abs(house[0] - i) + Math.abs(house[1] - j) < k)
                                    count++;

                        }

                        int money = count * m - work;

                        if (money >= 0 && count > max) {
                            max = count;
                        }

                    }
                }

            }
            sb.append('#').append(t).append(' ').append(max).append('\n');
        }
        System.out.println(sb);
    }
}

코드에 대한 피드백은 언제나 환영입니다🧚🏻‍♀️