5644. 무선충전

5644. 무선충전

시뮬레이션 문제. 조금 문제를 충실히 생각해봐야 했던 문제였다.

일단 내가 생각하던 x, y 좌표가 아니어서 내 방식으로 바꿔주는 부분에서도 헷갈렸다.

문제의 그림만 처음 봤을때는 BFS를 생각했지만, 문제 상에서 그냥 거리 D를 이용하면 따로 BFS를 사용하지 않아서 간단해졌다.

p[i][j] 를 통해서 i 시간에 좌표들의 위치를 저장하였다, 즉 j=0 일때는 0번 사람, j=1 일때는 1번 사람의 위치가 된다.

전체적인 흐름으로는 주어진 시간을 0초부터 끝까지 돌면서 각 점에서 닿을 수 있는 BC중 가장 Power 가 쌘놈을 찾는다. 단 이 과정에서 닿

을 수 있는 BC가 여러개인 놈을 체크하기 위해, cnt 라는 갯수를 세는 변수를 추가했다.

가장 쌘놈이 교집합일 때는 케이스를 나누어서 문제를 풀었다. (그 외에는 그냥 더하면 되므로)

0번 사람이 BC 1개, 1번 사람이 BC 1개 => 서로 하나의 BC를 나누어서 써야함.

0번 사람이 BC 2개 이상, 1번 사람이 BC 1개 => 0번 사람이 교집합를 BC를 양보.

0번 사람이 BC 1개, 1번 사람이 BC 2개 이상 => 1번 사람이 교집합인 BC를 양보.

0번 사람이 BC 2개 이상, 1번 사람이 BC 2개 이상 => 최대값을 파악해서 양보.

나는 처음에 빨간 부분을 인지하지 못하고 코드를 작성해서, 시간을 오래 잡아먹었다. 나는 무조건 0번 사람이 양보하는 방식으로 처음에 코

드를 짜서 틀렸는데, 최대값을 구하기 위해서는 2개 이상일 경우 최대를 구하는 방식으로 문제를 풀어야 한다.

조금 문제를 더럽게 푼 것같다.

<정답 코드>

#include<iostream>
#include<vector>
 
using namespace std;
 
typedef struct battery {
 
    int x;
    int y;
    int cover;
    int power;
 
}battery;
 
 
int dist(int x, int y, int x_, int y_)
{
    return abs(x - x_) + abs(y - y_);
}
 
 
 
int dx[5] = { 0,-1,0,1,0 };
int dy[5] = { 0,0,1,0,-1 };
int M, A;
int ans;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        cin >> M >> A;
 
        int x1, y1, x2, y2;
        ans = 0;
        x1 = 0;
        y1 = 0;
        x2 = 9;
        y2 = 9;
        vector<battery> b(A);
        vector<vector<pair<int, int>>> p(M + 1);
 
        p[0].push_back({ 0,0 });
        p[0].push_back({ 9,9 });
 
        //시간에 따른 사람의 위치 정보 저장
 
        for (int i = 0; i < 2; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                int tmp;
                cin >> tmp;
                if (i == 0)
                {
                    x1 += dx[tmp];
                    y1 += dy[tmp];
                    p[j].push_back({ x1,y1 });
                }
                else
                {
                    x2 += dx[tmp];
                    y2 += dy[tmp];
                    p[j].push_back({ x2,y2 });
                }
            }
 
        }
 
        //BC 정보 저장
 
        for (int i = 0; i < A; i++)
        {
            int tmp1, tmp2;
            cin >> tmp1 >> tmp2 >> b[i].cover >> b[i].power;
            b[i].x = tmp2 - 1;
            b[i].y = tmp1 - 1;
        }
 
 
 
        for (int i = 0; i <= M; i++)
        {
            int sum1 = 0, sum2 = 0;
            int cnt1 = 0, cnt2 = 0;
            int MAX = 0;
            int selected = -1;
 
            // i 초 일때 0번 사람이 닿을 수 있는 BC 체크
 
            for (int j = 0; j < A; j++)
            {
                int x, y, x_, y_;
                x = p[i][0].first;
                y = p[i][0].second;
                x_ = b[j].x;
                y_ = b[j].y;
 
                if (dist(x, y, x_, y_) <= b[j].cover)
                {
                    cnt1++;
                    if (b[j].power > MAX)
                    {
                        selected = j;
                        MAX = b[j].power;
                    }
                }
            }
            sum1 = MAX;
 
 
            // i 초 일때 1번 사람이 닿을 수 있는 BC 체크
 
            int selected2 = -2;
            MAX = 0;
            for (int j = 0; j < A; j++)
            {
                int x, y, x_, y_;
                x = p[i][1].first;
                y = p[i][1].second;
                x_ = b[j].x;
                y_ = b[j].y;
 
                if (dist(x, y, x_, y_) <= b[j].cover)
                {
                    cnt2++;
                    if (b[j].power > MAX) 
                    {
                        selected2 = j;
                        MAX = b[j].power;
                    }
                    
                }
            }
            sum2 = MAX;
            
 
            // 0번 사람과 1번 사람이 같은 BC를 공유할 때
 
            if (selected == selected2)
            {
                int sum1next = 0;
                int sum2next = 0;
 
 
                // 0번 사람과 1번 사람이 사용할 수 있는 BC가 1개 일때
                if (cnt1==1 && cnt2==1)
                {
                    ans += sum1;
                    continue;
                }
 
                // 0번 사람이 사용할 수 있는 BC가 2개 이상일 때, 맨 처음 구했던 최대 Power 다음의 값을 갖는 BC구하기
                if (cnt1 >= 2)
                {
                    MAX = 0;
                    for (int j = 0; j < A; j++)
                    {
                        int x, y, x_, y_;
                        x = p[i][0].first;
                        y = p[i][0].second;
                        x_ = b[j].x;
                        y_ = b[j].y;
 
                        if (j != selected && b[j].power > MAX && dist(x, y, x_, y_) <= b[j].cover)
                        {
                            MAX = b[j].power;
                        }
                    }
                    sum1next = MAX;
                }
 
                // 1번 사람이 사용할 수 있는 BC가 2개 이상일 때, 맨 처음 구했던 최대 Power 다음의 값을 갖는 BC구하기
                if (cnt2 >= 2)
                {
                    MAX = 0;
                    for (int j = 0; j < A; j++)
                    {
                        int x, y, x_, y_;
                        x = p[i][1].first;
                        y = p[i][1].second;
                        x_ = b[j].x;
                        y_ = b[j].y;
 
                        if (j != selected && b[j].power > MAX && dist(x, y, x_, y_) <= b[j].cover)
                        {
                            MAX = b[j].power;
                        }
                    }
                    sum2next = MAX;
                }
 
 
                // 0번 사람이 BC가 2개 이상일 때, 제일 Power 큰 BC를 1번 사람에게 양보
                if (cnt1 >= 2 && cnt2 == 1)
                    ans += (sum1next + sum2);
 
                // 1번 사람이 BC가 2개 이상일 때, 제일 Power 큰 BC를 0번 사람에게 양보
                if (cnt1 == 1 && cnt2 >= 2)
                    ans += (sum2next + sum1);
 
                // 0번과 1번 사람 모두 BC 2개 이상일때, 최대값을 구하기 위해 합의 최대값 찾기
                if (cnt1 >= 2 && cnt2 >= 2)
                {
                    if (sum1next > sum2next)
                        ans += (sum1next + sum2);
                    else
                        ans += (sum2next + sum1);
                }
 
            }
 
            //0번 사람과 1번 사람이 같은 BC를 공유하지 않을 때
 
            else
            {
                ans += (sum1 + sum2);
            }
 
 
 
 
        }
 
        cout << "#" << t << " " << ans << endl;
    }
 
 
    return 0;
}