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

자기 전에 풀고 자려고 하였으나...집중이 안 되어 문제만 읽다가 바로 자러간 문제!!!처음에 맵에 영역을 다 표시하여 영역 안에 집이 있는지 체크하려고 했으나..비효율 적인 느낌으로 잠이 들었따.

자고 일어나 눈을 빡 뜨니!!! 풀이가 떠올랐다. 예술가들의 영감이 이런것인가!!!!!!좌표에서 집들까지 거리가 계산 가능하니!! 이걸로 영역안에 집이 있는지 체크하면 되겠다!라는 생각이 들었다.

물론...이런 문제는 치킨 거리..같은 문제에서 풀어보았지만ㅋㅋㅋㅋㅋ

접근 법.

1. 집들을 구조에 배열 안에 저장해준다.

2. 홈 방범 서비스를 1~ N*2 까지 해주었다. N+1해도 통과는 되었지만..N을 다 덮을만한 크기의 홈 방법 서비스까지 체크해주어야 될 것 같아서 그랬다.

3. 그래고 홈 방범 서비스를 1,1~N,N까지 중심을 옮겨가며 서비스 중심으로 집까지의 거리가 n-1 이하인 집들의 개수를 카운트해준다.

3. 그리고 이익 따져주는 식에 넣어준 후 이익을 따져준다.

4. 마지막으로 여기가 중요하다. 나는 이익을 볼 때만을 판단해주어 1이상일 때만 MAX를 갱신해주었는데, 손실만 안 보면 되므려 이익이 0이상이면 MAX를 갱신해주면 끝!

#include <stdio.h>
#include <string.h>
 
typedef struct
{
    int y, x;
}point;
 
int abs(int a, int b)
{
    return a - b < 0 ? -1 * (a - b) : a - b;
}
 
int distance(int y1, int x1, int y2, int x2)
{
    return abs(y1, y2) + abs(x1, x2);
}
 
int Chage(int k)
{
    return k * k + (k - 1)*(k - 1);
}
 
int map[25][25], House_num, N, M, MAX;
point House[22 * 22];
 
 
int main()
{
    int Test_Case;
    scanf("%d", &Test_Case);
 
    for (int T = 1; T <= Test_Case; T++)
    {
        MAX = -1;
        memset(map, -1, sizeof(map));
        memset(House, 0, sizeof(House));
        House_num = 0;
        scanf("%d %d", &N, &M);
 
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                scanf("%d", &map[i][j]);
 
                if (map[i][j])
                {
                    House[House_num].y = i;
                    House[House_num++].x = j;
                }
            }
        }
 
        for (int n = 1; n <= N * 2 ; n++)//영역의 크기
        {
            int Ch = Chage(n);
 
            for (int a = 1; a <= N; a++)//영영의 y좌표 중간
            {
                for (int b = 1; b <= N; b++)//영역의 x좌표 중간
                {
                    int count = 0, benefit = 0;
 
                    for (int H = 0; H < House_num; H++)
                    {
                        if (distance(a, b, House[H].y, House[H].x) < n)
                        {
                            count++;
                        }
                    }
                    benefit = count * M - Ch;
 
                    if (benefit >= 0 && count > MAX)
                        MAX = count;
                }
            }
        }
 
 
        printf("#%d %d", T, MAX);
    }
 
    return 0;
}