[모의 SW 역량테스트] 5644. 무선 충전

[모의 SW 역량테스트] 무선 충전

---

1. 이해하기

• BC의 충전 범위가 C일 때, BC와 거리가 C 이하이면 BC에 접속할 수 있다.
  • 거리 = |Xa-Xb|+|Ya-Yb|
• 매초마다 특정 BC의 충전 범위 안에 들어오면 해당 BC에 접속이 가능하다. 만약 한 BC에 두 명의 사용자가 접속한 경우, 접속한 사용자의 수만큼 충전 양을 균등하게 분배한다.
• 모든 사용자가 충전한 양의 합의 최댓값을 구하는 문제.
• 시뮬레이션+완전 탐색 문제.

---

2. 구현하기

• 각 사용자를 움직인다.

  void move(int& x, int& y, int d) {
      x+=dx[d]; y+=dy[d];
  }

• 사용자가 모든 BC에 접속이 가능한지 보고, 그때 최대의 충전합을 구한다.

  int get_dist(int x, int y, int i) {
      return abs(x-bc[i].x)+abs(y-bc[i].y);
  }
  
  bool is_in_area(int x, int y, int i) {
      return get_dist(x,y,i) <= bc[i].c;
  }
  
  int get_max_charge_sum(int ax, int ay, int bx, int by) {
      int ret = 0;
      for(int i = 0; i < A; i++) {
          for(int j = 0; j < A; j++) {
              int sum = 0;
              if(i == j) {
                  if(is_in_area(ax,ay,i) or is_in_area(bx,by,i)) {
                      sum+=bc[i].p;
                  }
              } else {
                  if(is_in_area(ax,ay,i)) sum += bc[i].p;
                  if(is_in_area(bx,by,j)) sum += bc[j].p;
              }
              ret = max(ret,sum);
          }
      }
      return ret;
  }

• 각 초마다 사용자를 움직이고, 모두 움직인 후 합을 구해서 반환한다.

  int get_sum() {
      int ret = 0;
      for(int i = 0; i <= M; i++) ret += charge_amount[i];
      return ret;
  }
  
  int simulate(int ax, int ay, int bx, int by) {
      charge_amount[0] = get_max_charge_sum(ax,ay,bx,by);
      for(int i = 0; i < M; i++) {
          move(ax,ay,a_move[i]); move(bx,by,b_move[i]);
          charge_amount[i+1] = get_max_charge_sum(ax, ay, bx, by);
      }
      return get_sum();
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
struct INF{
    int x,y,c,p;
}bc[8];
int charge_amount[101];
int a_move[101], b_move[101];
int dx[] = {0,-1,0,1,0};
int dy[] = {0,0,1,0,-1};
int M,A;

void move(int& x, int& y, int d) {
    x+=dx[d]; y+=dy[d];
}

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

int get_dist(int x, int y, int i) {
    return abs(x-bc[i].x)+abs(y-bc[i].y);
}

bool is_in_area(int x, int y, int i) {
    return get_dist(x,y,i) <= bc[i].c;
}

int get_max_charge_sum(int ax, int ay, int bx, int by) {
    int ret = 0;
    for(int i = 0; i < A; i++) {
        for(int j = 0; j < A; j++) {
            int sum = 0;
            if(i == j) {
                if(is_in_area(ax,ay,i) or is_in_area(bx,by,i)) {
                    sum+=bc[i].p;
                }
            } else {
                if(is_in_area(ax,ay,i)) sum += bc[i].p;
                if(is_in_area(bx,by,j)) sum += bc[j].p;
            }
            ret = max(ret,sum);
        }
    }
    return ret;
}

int get_sum() {
    int ret = 0;
    for(int i = 0; i <= M; i++) ret += charge_amount[i];
    return ret;
}

int simulate(int ax, int ay, int bx, int by) {
    charge_amount[0] = get_max_charge_sum(ax,ay,bx,by);
    for(int i = 0; i < M; i++) {
        move(ax,ay,a_move[i]); move(bx,by,b_move[i]);
        charge_amount[i+1] = get_max_charge_sum(ax, ay, bx, by);
    }
    return get_sum();
}

void input() {
    cin >> M >> A;
    for(int i = 0; i < M; i++) cin >> a_move[i];
    for(int i = 0; i < M; i++) cin >> b_move[i];
    for(int i = 0; i < A; i++) cin >> bc[i].y >> bc[i].x >> bc[i].c >> bc[i].p;
}

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