[SWEA 5644] 무선 충전

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

[문제 출처] : SW Expert Academy [모의 SW 역량테스트] - 차량 정비소

 

[문제 풀이]

 

이번 문제는 시뮬레이션 + 완전 탐색 문제이다

이동 시간에 따른 이동 정보 즉 경로가 주어진다 시간의 정보는 주어지지 않고 또한 문제를 푸는 데 있어서  중요하지 않으며 주어진 이동 경로에 맞게 이동하면서 2명의 사용자가 얻을 수 있는 충전한 양의 합의 최댓값을 구하는 문제이다 

 

TMI) 

문제에서는 무조건 2명의 사용자가 이동하면서 얻을 수 있는 충전한 양의 합의 최댓값을 구하는 것이지만 여러 명의 사용자가 사용하는 것으로 문제를 구성했다면  조금 더 어려운 문제이지 않았나 생각이 된다. 그러한 문제 또한 사용자의 제한 범위가 크지 않다면 완전 탐색으로 풀 수 있지 않을까?

 

어떻게 풀었는지 풀이를 살펴보자!

 

다음 그림과 같이 임의적인 특정 상황을 가정하였다 

 

어디까지나 임의 적인 상황이다  위의 그림과 같은 위치에서 

 

A 사용자와 B 사용자는  다음과 같은 BC 구역을 이용 가능할 수 있다고 생각해보자

이러한 상황에서 어떤 것을 선택하는 것이 최대일까?  그냥 단순히 모든 경우의 수를 조합해보면 된다!

 

A사용자 : BC1 일 때   B사용자  : BC3 ~ BC7

A사용자 : BC2 일 때   B사용자  : BC3 ~ BC7

....

A사용자 : BC6 일때   B사용자  : BC3 ~ BC7

 

완전 탐색 후 최댓값을 찾을 수 있다 

 

이는 간단하게 2명의 사용자이기 때문에 2중 반복문을 사용해서 간단하게 구현이 가능하다   

 

당연히 문제에서 주어진 조건에 따라 같은 구역을 사용하는 경우는 사용자수에 따른 충전 양을 균등하게 나누어야 한다는 조건에 따라 적절하게 구현해 주면 된다

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int dy[] = { 0, 0, 1, 0, -1 };
const int dx[] = { 0, -1, 0, 1, 0 };
struct Battery {
    int y, x;
    int r, p;
};
vector<Battery> battery(10);
int ay = 1, ax = 1, by = 10, bx = 10;
int n, m;
void init() {
    ay = 1, ax = 1, by = 10, bx = 10;
}
int maxPower(vector<int>& bat) {
    int now = 0;
    for (int i = 0; i < bat.size(); i++) {
        now = max(now, battery[bat[i]].p);
    }
    return now;
}
int solve(vector<int>& ba, vector<int>& bb) {
    if (ba.size() == 0 && bb.size() == 0) return 0;
    if (ba.size() == 0) return maxPower(bb);
    if (bb.size() == 0) return maxPower(ba);
    int now = 0;
    for (int ia = 0; ia < ba.size(); ++ia) {
        int Pa = battery[ba[ia]].p;
        for (int ib = 0; ib < bb.size(); ++ib) {
            int Pb = battery[bb[ib]].p;
            if (bb[ib] == ba[ia]) now = max(now, (Pa + Pb) / 2);
            else now = max(now, (Pa + Pb));
        }
    }
    return now;
}
int main(int argc, char** argv) {
    int test_case, T;
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        cin >> n >> m;
        vector<int> pathA(n + 1);
        vector<int> pathB(n + 1);
        for (int i = 1; i <= n; i++) cin >> pathA[i];
        for (int i = 1; i <= n; i++) cin >> pathB[i];
        init();
        for (int i = 0; i < m; i++) {
            cin >> battery[i].y >> battery[i].x >> battery[i].r >> battery[i].p;
        }
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            ay += dy[pathA[i]];
            ax += dx[pathA[i]];
            by += dy[pathB[i]];
            bx += dx[pathB[i]];
            vector<int> ba, bb;
            for (int cnt = 0; cnt < m; ++cnt) {
                if (abs(ay - battery[cnt].y) + abs(ax - battery[cnt].x) <= battery[cnt].r) ba.push_back(cnt);
                if (abs(by - battery[cnt].y) + abs(bx - battery[cnt].x) <= battery[cnt].r) bb.push_back(cnt);
            }
            int now = solve(ba, bb);
            ans += now;
        }
        cout << "#" << test_case << " " << ans << "\n";
    }
    return 0;
}