2117 홈 방범 서비스

#include <stdio.h>
#include <string.h>
#include <vector>
#include <utility>
#include <stdlib.h>
#include <algorithm>
 
using namespace std;
 
//static variable
int cen_x = 40, cen_y = 40;
 
// variable
int width, pay;
int tmp_home[100][100];
int rst_cnt;
vector<pair<int, int> > home;
 
// function
void initialize();
void protect(int len);
 
int main() {
    int test;
    scanf("%d", &test);
 
    for (int t = 1; t <= test; t++) {
        initialize();
 
        for (int i = 1; i <= width+1; i++)
            protect(i);
 
        printf("#%d %d\n", t, rst_cnt);
    }
}
 
void protect(int len) {
    int cost = 2 * len * len - 2 * len + 1;
 
    for (int i = cen_x - len + 1; i < cen_x + width + len + 1; i++) {
        for (int j = cen_y - len + 1; j < cen_y + width + len + 1; j++) {
            int tmp_cnt = 0;
            for (int k = 0; k < home.size(); k++) {
                int y = home[k].first;
                int x = home[k].second;
                int home_len = abs(y - i) + abs(x - j);
 
                if (len > home_len)
                    tmp_cnt++;
            }
 
            // 보상 비용 손해가 없는가?
            int profit = pay * tmp_cnt;
            if (profit < cost)
                continue;
 
            rst_cnt = max(rst_cnt, tmp_cnt);            
        }
    }
//        printf("\n");
 
}
 
void initialize() {
    // scanf
    scanf("%d %d", &width, &pay);
 
    // memset
    memset(tmp_home, 0, sizeof(tmp_home));
    
    // vector
    home.clear();
 
    // arr
    for (int i = cen_y + 1; i <= cen_y + width; i++)
        for (int j = cen_x + 1; j <= cen_x + width; j++) {
            scanf("%d", &tmp_home[i][j]);
 
            if (tmp_home[i][j] == 1)
                home.push_back(make_pair(i, j));
        }
 
    // variable
    rst_cnt = -1;
}
 
 

간단한 for 문 여러개를 돌리면 되는 문제였다

abs 를 이용하여 각각의 집의 거리를 계산하는게 주효했으며,

처음부터 각 집의 위치를 벡터에 저장해서 시간 단축을 하려 했던게 먹혔던거같다.