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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

문제정리

1. 홈방범 서비스는 마름모 모양의 영역에서만 제공된다.

2. 운영 비용 = K * K + (K - 1) * (K - 1) , K는 1 이상의 정수이다.

3. 홈방범 서비스를 제공받는 집들은 각각 M의 비용을 지불할 수 있어, 손해를 보지 않는 한 최대한 많은 집에

홈방법 서비스를 제공하려고 한다.

4. 도시의 크기 N과 하나의 집이 지불할 수 있는 비용 M, 도시의 정보가 주어진다.

이때, 손해를 보지 않으면서 홈방범 서비스를 가장 많은 집들에 제공하는 서비스 영역을 찾고, 그 때의

홈방범 서비스를 제공 받는 집들의 수를 출력하는 프로그램을 작성하라.

5. 보안회사의 이익 = 서비스 제공받는 집들을 통해 얻는 수익 - 운영 비용

문제issue

1. N의 크기에 따라 K의 크기를 어디까지 결정??

- 마름모의 크기가 map전체를 덮는 경우까지 봐야해서 K = N + 1까지 살펴봐야 한다.

2. 마름모표현

- 마름모의 특징은 중앙에서 모든 곳의 거리가 같다.

3. 보안회사의 이익 = 0 이면 손해인건가 아닌건가??

- '손해를 보지 않으면서 홈방범 서비스를~' 이 부분에서 0은 손해가 아니라는 사실을 유추할 수 있지만

조금은 애매하다고 생각하기 때문에 만약 실제 소검이었다면 주저하지말고 질문하도록 하자

해결흐름

1. map에서 모든 셀을 마름모의 중심으로 하여 살펴본다.

2. 마름모의 중앙이 i, j라고 할 때 map을 다시 살펴볼 l, m과의 관계에서 Math.abs(i-l) + Math.abs(j - m) <= k - 1

이라면 마름모의 범위이다. 이때 map[l][m] = 1인 곳을 카운트 해줘서 마름모 범위안의 집의 수를 구한다.

3. 이익을 구한 뒤 0 이상이면 집의 최댓값을 갱신해준다.

소스코드

x
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
​
public class Solution {
​
    private static int N;
    private static int M;
    private static int[][] map;
    private static int home;
    private static int result;
​
    public static void main(String[] args) throws Exception {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int test_case = Integer.parseInt(br.readLine().trim());
        for (int tc = 1; tc <= test_case; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            N = Integer.parseInt(st.nextToken()); // k의 최댓값 = N + 1
            M = Integer.parseInt(st.nextToken()); // 하나의 집이 지불할 수 있는 비용
            map = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine().trim());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            result = Integer.MIN_VALUE;
            for (int k = 1; k <= N + 1; k++) {
                // i,j 한개가 마름모의 중심
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        home = 0;
                        solve(k, i, j);
                    }
                }
            }
            System.out.println("#" + tc + " " + result);
        } // end of tc
    } // end of main
​
    private static void solve(int k, int i, int j) {
        for (int l = 0; l < N; l++) {
            for (int m = 0; m < N; m++) {
                // 마름모의 범위이면서 1인 곳 카운트
                if (Math.abs(i - l) + Math.abs(j - m) <= k - 1 && map[l][m] == 1) {
                    home++;
                }
            }
        }
        int benefit = (home * M) - (k * k + (k - 1) * (k - 1));
        if(benefit >= 0) {
            if(result < home)
                result = home;
        }
    }
} // end of class