SWEA2117.md

홈 방범 서비스

https://swexpertacademy.com/ [2117]

개요

N*N크기의 map에 집들이 있다. 맵에 마름모모양으로 방범 서비스를 제공한다. 마름모모양 안에 있는 집의 수*M 만큼의 수익을 얻고 마름모모양만큼의 비용이 필요하다. 비용이 수익과 같거나 작을 경우에만 서비스를 제공할 때 서비스를 제공받는 집의 수의 최댓값을 구하는 문제

분석

단순히 모든 경우를 살피며 따져줘도 시간제한 내에 풀 수 있다. 더 좋은 알고리즘이 있을 것 같지만 떠오르지 않는다.

알고리즘

1. i, j를 선택한다.

2. k를 1부터~2*n까지 바꾸어가며 마름모영역을 늘려간다.

3. 비용<=수익 이면 집의 최대개수(수익/m)를 갱신한다.

소스

#include <stdio.h>
#include <malloc.h>
 
int bang[4][2] = { { 1, -1 }, { -1, -1 }, { -1, 1 }, { 1, 1 } };
 
int bc(int r, int c, int n)
{
    if (r < n&&r >= 0 && c < n &&c >= 0) return 1;
    return 0;
}
 
int process(int n, int m, int **map)
{
    int cost, i, j, k,l, max, nx, ny, answer=0, ct, su;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            nx = i;
            ny = j;
            cost = 1;
            su = 0;
            max = 0;
            if (map[nx][ny] == 1) su+=m;
            if (cost <= su) max = su;
            for (k = 2; k < 2*n; k++)
            {
                cost = k * k + (k - 1) * (k - 1);
                ny += 1;
                for (l = 0; l < 4; l++)
                {
                    ct = 0;
                    while (ct<k-1)
                    {
                        ct++;
                        nx = nx + bang[l][0];
                        ny = ny + bang[l][1];
                        if (bc(nx, ny, n) && map[nx][ny] == 1) su += m;
                    }
                }
                if (cost <= su) max = su;
            }
 
            if (answer < max) answer = max;
        }
    }
    return answer/m;
 
}
 
int main()
{
    int T, N, M, *answer, i, j, k, **map;
 
    scanf("%d", &T);
 
    answer = (int*)malloc(sizeof(int)*T);
 
    for (i = 0; i < T; i++)
    {
        scanf("%d%d", &N, &M);
 
        map = (int**)malloc(sizeof(int*)*N);
        for (j = 0; j < N; j++)
        {
            map[j] = (int*)malloc(sizeof(int)*N);
            for (k = 0; k < N; k++) scanf("%d", &map[j][k]);
        }
 
        answer[i]=process(N, M, map);
 
        for (j = 0; j < N; j++) free(map[j]);
        free(map);
    }
 
    for (i = 0; i < T; i++) printf("#%d %d\n", i + 1, answer[i]);
    free(answer);
 
    return 0;
}