[SWEA 5644] 무선충전

문제풀이

상당히 어렵게 푼 문제이다. 단순히 구현하는 문제(시뮬레이션)인데 공유하는 BC가 있을경우 선택을 잘 해야한다.

유저 a와 b의 경로를 2차원 배열에 저장하고 이동이 끝나면 시작위치의 좌표를 재조정한다.

이때 1) 유저 a만 충전하는 경우 2) 유저 b만 충전하는 경우 3) 유저 a,b 모두 충전하는 경우

총 3가지로 나누어 처리하였다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef struct BC{
    int x, y, c, p;
}BC;
vector<BC> bc;
int ax, ay, bx, by;
int m, a, c, p;
int chargeA, chargeB;
// 정지, 상, 우, 하, 좌
int dx[]={0, 0, 1, 0, -1};
int dy[]={0, -1, 0, 1, 0};
int userPath[2][101];
 
int solve() {
    ax=ay=1;
    bx=by=10;
    chargeA=chargeB=0;
 
    for (int k=0; k<=m; k++) {
        vector<int> a,b;
        for (int i=0; i<bc.size(); i++) {
            if (abs(ax - bc[i].x) + abs(ay - bc[i].y) <= bc[i].c) 
                a.push_back(i);
            if (abs(bx - bc[i].x) + abs(by - bc[i].y) <= bc[i].c) 
                b.push_back(i);
        }
 
        int pA=0, pB=0, tmpSum=0;
        if (!a.empty() && b.empty()) {
            for (int i=0; i<a.size(); i++) {
                int tmpA = bc[a[i]].p;
                if (tmpSum < tmpA) {
                    tmpSum = tmpA;
                    pA = tmpA;
                }
            }
        }
        else if (a.empty() && !b.empty()) {
            for (int i=0; i<b.size(); i++) {
                int tmpB = bc[b[i]].p;
                if (tmpSum < tmpB) {
                    tmpSum = tmpB;
                    pB = tmpB;
                }
            }
        }
        else {
            for (int i=0; i<a.size(); i++) {
                for (int j=0; j<b.size(); j++) {
                    int tmpA = bc[a[i]].p;
                    int tmpB = bc[b[j]].p;
                    if (a[i] == b[j]) {
                        tmpA/=2;
                        tmpB/=2;
                    }
                    if (tmpSum < tmpA+tmpB) {
                        tmpSum = tmpA+tmpB;
                        pA = tmpA;
                        pB = tmpB;
                    }
                }
            }
        }
 
        ax += dx[userPath[0][k]];
        ay += dy[userPath[0][k]];
        bx += dx[userPath[1][k]];
        by += dy[userPath[1][k]];
        chargeA += pA;
        chargeB += pB;
    }
    return chargeA + chargeB;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc;
    cin>>tc;
    for (int t=1; t<=tc; t++) {
        cin>>m>>a;
        memset(userPath[0], 0, sizeof(userPath[0]));
        memset(userPath[1], 0, sizeof(userPath[1]));
        bc.clear();
 
        for (int i=0; i<m; i++) cin>>userPath[0][i];
        for (int i=0; i<m; i++) cin>>userPath[1][i];
 
        int y, x;
        for (int i=0; i<a; i++) {
            cin>>x>>y>>c>>p;
            bc.push_back(BC{x, y, c, p});
        }
 
        cout<<"#"<<t<<" "<<solve()<<"\n";
    }
    return 0;
}