[C++] SWEA 5644 - 무선 충전

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

SW Expert Academy

<풀이>

1. 사용자 A, B의 좌표를 한번씩 이동시킨다.

2. 이동할 때 마다 사용자들과 모든 BC의 거리를 계산 후, 사용 가능한 BC의 정보를 각각 벡터에 저장한다.

3. A와 B가 사용할 모든 BC의 경우를 판단하여, 가장 큰 충전량의 합을 계산한다.

4. 결과를 출력한다.

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
//구조체 : BC 정보
struct BC {
    int x, y;
    int c;
    int p;
};
 
//5방향
int di[] = { 0,-1,0,1,0 };
int dj[] = { 0,0,1,0,-1 };
 
int M, BC_cnt;
int A[101];
int B[101];
vector<BC> bc;
int res;
 
int main() {
 
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        bc.clear();
        res = 0;
 
        //입력
        cin >> M >> BC_cnt;
        for (int i = 1; i <= M; i++) {
            cin >> A[i];
        }
        for (int i = 1; i <= M; i++) {
            cin >> B[i];
        }
        for (int i = 0; i < BC_cnt; i++) {
            int x, y, c, p;
            cin >> y >> x >> c >> p;
            bc.push_back({ x,y,c,p });
        }
 
        //A가 사용할 수 있는 BC, B가 사용할 수 있는 BC 저장 벡터
        vector<int> a_BC, b_BC;
 
        //A,B 초기 좌표
        int ax = 1, ay = 1, bx = 10, by = 10;
 
        //시간마다 탐색
        for (int i = 0; i <= M; i++) {
 
            a_BC.clear();
            b_BC.clear();
 
            //A좌표, B좌표
            ax += di[A[i]];
            ay += dj[A[i]];
            bx += di[B[i]];
            by += dj[B[i]];
 
            //모든 BC와 거리 구하기
            for (int j = 0; j < BC_cnt; j++) {
                int a_dist = abs(ax - bc[j].x) + abs(ay - bc[j].y);
                int b_dist = abs(bx - bc[j].x) + abs(by - bc[j].y);
 
                //사용할 수 있는 거리라면 벡터에 저장
                if (a_dist <= bc[j].c) {
                    a_BC.push_back(j);
                }
                if (b_dist <= bc[j].c) {
                    b_BC.push_back(j);
                }
            }
 
            //A와 B가 모두 사용할 수 있는 BC가 있는 경우(BC가 겹치는 경우 처리)
            if (!a_BC.empty() && !b_BC.empty()) {
 
                //두 개의 합 중 가장 큰 값 구해서 더해주기
                int maxSum = 0;
                for (int k = 0; k < a_BC.size(); k++) {
                    for (int l = 0; l < b_BC.size(); l++) {
 
                        int tmpA = bc[a_BC[k]].p;
                        int tmpB = bc[b_BC[l]].p;
 
                        if (a_BC[k] == b_BC[l]) {
                            tmpA /= 2;
                            tmpB /= 2;
                        }
 
                        int tmpSum = tmpA + tmpB;
                        if (tmpSum > maxSum) {
                            maxSum = tmpSum;
                        }
                    }
                }
                res += maxSum;
            }
            //A만 사용할 수 있는 BC가 있는 경우
            else if (!a_BC.empty()) {
                //A가 사용할 수 있는 최대값 구해서 더해주기
                int maxA = 0;
                for (int k = 0; k < a_BC.size(); k++) {
                    if (bc[a_BC[k]].p > maxA) {
                        maxA = bc[a_BC[k]].p;
                    }
                }
                res += maxA;
            }
            //B만 사용할 수 있는 BC가 있는 경우
            else if (!b_BC.empty()) {
                //B가 사용할 수 있는 최대값 구해서 더해주기
                int maxB = 0;
                for (int k = 0; k < b_BC.size(); k++) {
                    if (bc[b_BC[k]].p > maxB) {
                        maxB = bc[b_BC[k]].p;
                    }
                }
                res += maxB;
            }
        }
 
        //결과 출력
        cout << "#" << test_case << " " << res << "\n";
    }
    return 0;
}

 

구현에 대해 알아볼 수 있는 문제였습니다.