[SW Expert 5644] 무선 충전

#문제

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

#풀이

오랜만에 SW Expert에서 문제를 풀었더니...너무 힘들었습니다. 
굉장히 쉬운 문제로 보였으나... 푸는 시간이 너무나도 오래 걸렸습니다.
해당 문제는 완전 탐색으로 풀 수 있습니다. 
맵의 크기도 10 * 10이며, BC의 개수도 8개로 작기 때문에 가능합니다.

풀이의 핵심은 시간마다 A,B 따로따로 충전량을 저장하는 것이 아닌 합쳐서 비교합니다.
어차피 마지막에 모든 충전량을 다 더해 주어야기 때문에 이런 방법으로 할 수 있는 것이죠.

일단, A와 B가 해당 위치에서 충전을 받을 수 있는 BC들을 구합니다.
거리 안에 있는 BC들의 충전량을 따로 저장한 뒤 해당 위치에서 할 수 있는 최대 충전량을 구합니다.

이때는 모든 BC들을 돌며 비교를 해야합니다. 
만약 같은 위치의 숫자가 있다면, 해당 시간에 A와 B는 같은 BC안에 있는 것입니다.
따라서 같은 위치의 있을 경우는 그냥 한 곳에 충전량만 확인하면 됩니다.
굳이 2로 나누고 그걸 합쳐도 한명의 충전량과 같기 때문이죠.
그리고 여기서 중요한 점은 A만 확인하면 안된다는 것입니다. 같은 위치에 있더라도 만약 A가 0 B가 70이면, 70을 골라야 하기 때문이죠. 그렇기에 B의 값도 최대값인지 확인해줍니다.

만약 같은 위치가 아니라면 A의 충전량과 B의 충전량 모두 더해 비교를 해줍니다. 

하나 더 놓칠 수 있는 부분은 바로 처음 위치에서도 확인을 해주어야된다는 점입니다. 
꼭 확인해 주세요 :)

그리고 BC인데 왜 AP로 했는지...왜 그랬을까...의문이 드네요ㅎㅎ

#코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
class AP{
public:
    int x;
    int y;
    int c;
    int p;
};
int M,A;
//방향은 5개, 0일때가 추가됨.
int dx[5] = {0,0,1,0,-1};
int dy[5] = {0,-1,0,1,0};
 
//해당 위치에서 A,B의 파워 검색
int checkPoint(vector<AP> APs, int ax, int ay, int bx, int by){
    //먼저 A,B가 전파를 받을 수 있는 곳에 충전 가능한 정도를 저장.
    vector<int> possibleA(A,0);
    vector<int> possibleB(A,0);
    
    for(int i = 0; i < A; i++){
        int distA = abs(APs[i].x - ax) + abs(APs[i].y - ay);
        int distB = abs(APs[i].x - bx) + abs(APs[i].y - by);
        if(distA <= APs[i].c) possibleA[i] = APs[i].p;
        if(distB <= APs[i].c) possibleB[i] = APs[i].p;
    }
    //구해야 할 것은 해당 시간에서 A,B가 받을 수 있는 충전량을 모두 더하는 것.
    //따라서 미리 해당 시간에서 최대치를 저장해둔다.
    //만약 i == j 즉, 같은 AP에서 충전을 받을 경우 합계는 한개 값과 같다.(어차피 나누기하여 더해도 하나의 값)
    //또한 같은 위치에 있는 모든 수를 비교해야하므로 A가 클지 B가 클지 모르므로 다 비교.
    //같지 안을때는 무조건 더해서 비교하므로 나누기 2를하고 곱하기 2를 하고를 생각할 필요가 없음.
    int sum = 0;
    for(int i = 0; i < A; i++){
        for(int j = 0; j < A; j++){
            if(i == j){
                sum = max(sum, possibleA[i]);
                sum = max(sum, possibleB[i]);
            }else{
                sum = max(sum , possibleA[i] + possibleB[j]);
            }
        }
    }
    return sum;
}
 
int main(){
    int T;
    cin >> T;
    for(int tc = 1; tc <= T; tc++){
        cin >> M >> A;
        vector<int> routeA;
        vector<int> routeB;
        for(int i = 0; i < M; i++){
            int a;
            cin >> a;
            routeA.push_back(a);
        }
        for(int i = 0; i < M; i++){
            int a;
            cin >> a;
            routeB.push_back(a);
        }
        vector<AP> APs;
        for(int i = 0; i < A; i++){
            AP ap;
            cin >> ap.x >> ap.y >> ap.c >> ap.p;
            APs.push_back(ap);
        }
        //초기 위치에서도 확인을 해야한다.
        int ax = 1, ay = 1;
        int bx = 10, by = 10;
        int ans = checkPoint(APs,ax,ay,bx,by);
        //그 후에 A,B의 경로를 따라 매번 확인해 주며, 제일 큰 값이 리턴되므로 계속해서 더해준다.
        for(int i = 0; i < M; i++){
            ax += dx[routeA[i]];
            ay += dy[routeA[i]];
            bx += dx[routeB[i]];
            by += dy[routeB[i]];
            ans += checkPoint(APs,ax,ay,bx,by);
        }
        cout << "#" <<tc <<" " << ans << endl;
    }
    return 0;
}