[SWEA] 무선충전

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo

SW Expert Academy

[풀이]

 

1) 사용자는 2명, 충전소는 여러 좌표에 위치해 있다. 

 

2) 각 사용자는 주어진 이동 방향에 따라 이동한다. 

 

3) 맨해튼 거리 공식 ( 좌표 A, B가 있을 때, |A.x - B.x| + |A.y - B.y| 가 충전소의 충전범위 내에 있다면 충전을 한다. )

 

4) 두 명이 동시에 한 충전소에서 충전을 하게 될 경우 접속한 사용자의 수만큼 균등하게 충전이 된다. 

 

5) 두 명의 충전한 충전량의 최대값을 구하는 것이기 때문에 균등하게 나누지 않고 한 명이 모두 충전하는 것으로 계산해야 한다. 

 

6) 각 사용자는 지도의 양 끝에서 출발한다. => 이동 방향에 따라서 이동하면서 충전소의 충전 범위 내에 들어가는지 확인한다. 

 

7) 한 충전소에 여러 번 충전되는 것을 방지하기 위해 visited 배열을 사용 

 

* chk[9][2] => 사용자는 2명 / 충전소는 최대 9개 

* userMove[2][101] => 사용자는 2명 / 최대 100시간동안 움직임 

 

* charge() => 각 충전소에서 사용자들이 충전한 최대 충전량을 반환한다. 

* moveUsers() => 사용자들을 이동시킨다. 

 

* 유의할 점 

x와 y좌표를 평면 좌표로 생각해야 한다. (상 -> y-- / 좌 -> x++ ...)

---

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129

#include <iostream> #include <vector> #include <cstring> using namespace std;   typedef struct User {     int x, y; } U; typedef struct BC {     int x, y, c, p;   } B; B bcs[9]; //1개 이상 8개 이하 int dx[5] = {0, 0, 1, 0, -1}, dy[5] = {0, -1, 0, 1, 0}; //상우하좌 U user[2]; int userMove[2][101]; int m, a; bool chk[9][2];   int max(const int &a, const int &b) {     if (a > b)         return a;     return b; } int charge() {       int maxx = 0;     for (int i = 0; i < a; i++)     {         for (int j = 0; j < a; j++)         {             int res = 0;             if (chk[i][0])             {                 if (chk[j][1])                 {                     res = i == j ? bcs[j].p : bcs[i].p + bcs[j].p;                 }                 else res = bcs[i].p;                                   }             else {                 if (chk[j][1])                     res = bcs[j].p;             }             maxx = max(maxx, res);         }     }     return maxx; } int moveUsers() {     user[0].x = 1;     user[0].y = 1;     user[1].x = 10;     user[1].y = 10;       int ans = 0;     for (int i = 0; i <= m; i++)     {         //movement를 움직임         for (int j = 0; j < 2; j++)         {             user[j].x += dx[userMove[j][i]];             user[j].y += dy[userMove[j][i]];         }         memset(chk, 0, sizeof(chk));           for (int j = 0; j < a; j++)         {             int dist1 = abs(user[0].x - bcs[j].x) + abs(user[0].y - bcs[j].y);             if (dist1 <= bcs[j].c && !chk[j][0])             {                 chk[j][0] = 1;             }             int dist2 = abs(user[1].x - bcs[j].x) + abs(user[1].y - bcs[j].y);             if (dist2 <= bcs[j].c && !chk[j][1])             {                 chk[j][1] = 1;             }         }           ans += charge();               }     return ans; } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       int t;     cin >> t;       for (int tc = 1; tc <= t; tc++)     {           cin >> m >> a;         for (int j = 0; j < 2; j++)         {             for (int i = 1; i <= m; i++)             {                 cin >> userMove[j][i];             }         }           int x, y, c, p;         for (int i = 0; i < a; i++)         {             cin >> x >> y >> c >> p;             bcs[i].x = x;             bcs[i].y = y;             bcs[i].c = c;             bcs[i].p = p;         }           cout << "#" << tc << " " << moveUsers() << '\n';               }       return 0; }