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

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

---

1. 이해하기

• 홈방법 서비스를 제공하기 위해서는 운영 비용이 필요하다.
  • 운영 비용 = (K*K) + (K-1) * (K-1)
• 홈방범 서비스를 제공받는 집들은 각각 M의 비용을 지불할 수 있다.
• 보안회사에서는 손해를 보지 않는 한 최대한 많은 집에 홈방법 서비스를 제공하려고 한다.
  • 손해를 보지 않는 다는 말은 이익이 0이어도 제공한다는 뜻이다.
• 홈방법 서비스를 제공 받는 집들의 수를 출력하는 문제.
• 완전탐색 문제.

---

2. 구현하기

• 서비스를 제공하는 크기가 K일 때, 운영 비용을 구한다.

  int get_oper_cost(int k) {
      return (k*k)+((k-1)*(k-1));
  }

• 홈방범 서비스를 제공하는 시작 지점과 집과의 거리를 구해, 제공할 수 있는 집인지 체크하고 그 때의 수익을 구한다.

  int abs(int a) {
      return (a<0)?-a:a;
  }
  
  int get_dist(int x, int y, int x1, int y1) {
      return abs(x-x1)+abs(y-y1);
  }
  
  int get_profit(int x, int y, int k) {
      int cnt = 0;
      for(int i = 0; i < house_index; i++) {
          Point now = house[i];
          if(get_dist(now.x,now.y,x,y) < k) cnt++;
      }
      return cnt*M;
  }

• 운영 비용과 수익의 차이를 구하고 손해를 보지 않는지 체크한다.

  bool is_profit(int x, int y, int k) {
      return (get_profit(x,y,k)-get_oper_cost(k)) >= 0;
  }

• 모든 지역을 포괄하는 K까지 살펴보면서 홈방범 서비스를 제공 받는 집 수의 최댓값을 구한다.

  int simulate() {
      int ret = 0;
      for(int k = 1; k <= N+N/2; k++) {
          for(int i = 0; i < N; i++) {
              for(int j = 0; j < N; j++) {
                  if(is_profit(i,j,k)) {
                      ret = max(ret,get_profit(i,j,k)/M);
                  }
              }
          }
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <cstring>
using namespace std;
struct Point{
    int x,y;
};
int map[20][20];
Point house[400];
int house_index;
int N,M;

int abs(int a) {
    return (a<0)?-a:a;
}

int get_oper_cost(int k) {
    return (k*k)+((k-1)*(k-1));
}

int get_dist(int x, int y, int x1, int y1) {
    return abs(x-x1)+abs(y-y1);
}

int get_profit(int x, int y, int k) {
    int cnt = 0;
    for(int i = 0; i < house_index; i++) {
        Point now = house[i];
        if(get_dist(now.x,now.y,x,y) < k) cnt++;
    }
    return cnt*M;
}

bool is_profit(int x, int y, int k) {
    return (get_profit(x,y,k)-get_oper_cost(k)) >= 0;
}

int simulate() {
    int ret = 0;
    for(int k = 1; k <= N+N/2; k++) {
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(is_profit(i,j,k)) {
                    ret = max(ret,get_profit(i,j,k)/M);
                }
            }
        }
    }
    return ret;
}

void input() {
    memset(house,0,sizeof(house));
    house_index = 0;
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
            if(map[i][j] == 1) house[house_index++] = {i,j};
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        cout << '#' << t << ' ' << simulate() << '\n';
    }
    return 0;
}