[SWEA] 2117. 홈 방범 서비스 - Simulation

[SWEA] 2117. 홈 방범 서비스 - Simulation

제출일 : 2019-11-12

문제 풀이 시간 : 1H

난이도 : ★★

Problem

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

Constraints

1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 3초

2. 도시의 크기 N은 5 이상 20 이하의 정수이다. (5 ≤ N ≤ 20)

3. 홈방범 서비스의 운영 비용은 서비스 영역의 면적과 동일하다.

4. 도시에는 최소 1개 이상의 집이 존재한다.

input

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

Output

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

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

Example

input

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
…

output

#1 5
…

Solution & Inpression

모의 SW 역량테스트문제 중 가장 쉬웠던 문제인것 같다.

핵심은 마름모를 만드는것.
$$
if ((Math.abs(i - r) + Math.abs(j - c)) <= k - 1)
$$

Code

언어 : JAVA

메모리 : 45,780 kb

실행시간 : 499 ms

import java.util.Scanner;

public class Solution {
    static int N, M;
    static int[][] map;
    static int max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            N = sc.nextInt(); // 도시 크기
            M = sc.nextInt(); // 하나의 집이 지불할 수 있는 비용

            map = new int[N][N];
            int c = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    int tmp = sc.nextInt();
                    map[i][j] = tmp; // 집이면 1
                    if (tmp == 1) {
                        c++;
                    }
                }
            }

            max = Integer.MIN_VALUE;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (c == max)
                        break;
                    solve(i, j);
                }
            }

            System.out.println("#" + tc + " " + max);
        }
        sc.close();
    }

    private static void solve(int r, int c) {
        for (int k = 1; k <= N + N; k++) {
            int cnt = 0;
            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    if ((Math.abs(i - r) + Math.abs(j - c)) <= k - 1)
                        if (map[i][j] == 1)
                            cnt++;

            int cost = k * k + (k - 1) * (k - 1);
            if (cost <= cnt * M)
                if (max < cnt)
                    max = cnt;
        }
    }

}