[SWEA] 2117. 홈 방범 서비스

2117 홈 방범 서비스

풀이)

각 칸 좌표마다 마름모 범위만큼 둘러봐. 집들의 개수 세어 풀었다.

마름모 범위(k) 설정은 1부터 n+1(혹시 몰라 n보다 크게)까지했다.

주의점

이거 때문에 어이없게 틀렸었다.

손해를 보지 않으면서 가장 많은 집에게 홈방범 서비스를 제공한다. 라는 뜻이

이익이 0이여도 된다는 얘기였다.

즉, 처음에는 profit > cost 로 풀어서 틀렸는데

profit >= cost 로 계산해야 한다는 것이다.

코드)

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n,m;
int map[20][20];
int result;
int cost;
void check(int y, int x, int len) {
    int cnt = 0;//범위 내의 집개수
    
    int fy = y, sy = y;
    int fx = x - len, sx = x + len;
 
    //가운데
    for (int i = fx; i <= sx; i++) {
        if (i >= 0 && i < n && map[y][i] == 1)cnt++;
    }
    while (len>=1)
    {
        fy = fy - 1;
        sy = sy + 1;
        fx = fx + 1;
        sx = sx - 1;
 
        //위쪽
        if (fy >= 0) {
            for (int i = fx; i <= sx; i++) {
                if (i >= 0 && i < n && map[fy][i] == 1)cnt++;
            }
        }
        //아래쪽
        if (sy < n) {
            for (int i = fx; i <= sx; i++) {
                if (i >= 0 && i < n && map[sy][i] == 1)cnt++;
            }
        }
        len--;
    }
    int profit = cnt * m;
    
    if (profit - cost >= 0) {
        result = max(result, cnt);
    }
}
 
int main() {
    //freopen("sample_input.txt", "r", stdin);
    int T = 0;
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++) {
        scanf("%d %d", &n, &m);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &map[i][j]);
            }
        }
        //k가 1일때 운영비용 = 1
        if (m >= 1) result = 1;
        //k가 2
        for (int t = 1; t <= n; t++) {
            cost = (t + 1)* (t + 1) + t * t;//운영비용
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    check(i, j, t);
                }
            }
        
        }
        printf("#%d %d\n", test_case, result);
        result = 0;
    }
    return 0;
}