[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++ ...)

---

#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; }