[SWEA][모의 SW 역량테스트][C++] 5644 무선 충전

문제

SWEA 모의 SW 역량테스트 - 5644 무선 충전

SW Expert Academy

 

---

문제 풀이

접근 방식

두 사람이 충전기(BC)가 설치된 지역을 돌아다니면서 얻게되는 충전량의 최댓값을 구하는 문제이다.

같은 충전기를 사용하면 충전량은 각각 반으로 나눠지기 때문에 이를 고려하여 문제를 해결해야한다.

 

우선, map을 3차원 벡터로 만들어서 각 BC의 충전 범위에 P(성능, 충전량)를 표시해주었다.

이 충전 범위는 이전 문제였던 홈 방범 서비스에서의 서비스 영역과 같은 모양이어서

이때 작성했던 2중 for문을 활용하였다.

[SWEA][모의 SW 역량테스트][C++] 2117 홈 방범 서비스

 

그런 다음, 시간에 따라 사람을 이동시키며 각 시간마다의 최대 충전량을 구해주었다.

(0초에도 충전이 되기 때문에 0초에서 시작해야한다.)

각 초마다 이동하는 방향에 따라 사람을 이동시켜주었고,

그 위치가 BC의 충전 범위라면 각각 BC1, BC2에 해당 인덱스를 넣어 모든 조합을 탐색하여 최댓값을 구해주었다.

(어떤 BC의 충전 범위도 아닌 경우에는 인덱스로 0을 넣어서 P가 0인 경우로 설정해주었다.)

그렇게 모든 시간에서의 최댓값을 모두 더해 최종적인 답을 구하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
int main(int argc, char **argv)
{
    int test_case, i, j, a, b, c, total, result;
    int T, M, A, X, Y, C, P;
    int x1, y1, x2, y2, len1, len2, MAX;
    int map[11][11][9];
    int user1[101];
    int user2[101];
    vector<int> BC1;
    vector<int> BC2;
    int dir[5][2] = {{0, 0}, {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case)
    {
 
        // 입력 받기 & map에 충전 범위 표시
        memset(user1, 0, sizeof(user1));
        memset(user2, 0, sizeof(user2));
        memset(map, 0, sizeof(map));
 
        cin >> M >> A;
        for (i = 1; i <= M; i++)
        {
            cin >> user1[i];
        }
        for (i = 1; i <= M; i++)
        {
            cin >> user2[i];
        }
 
        for (i = 1; i <= A; i++)
        {
            cin >> Y >> X >> C >> P;
            c = 0;
            for (a = X - C; a <= X + C; a++)
            {
                for (b = Y - c; b <= Y + c; b++)
                {
                    if (a < 1 || a > 10 || b < 1 || b > 10)
                        continue;
                    map[a][b][i] = P;
                }
                if (a < X)
                    c++;
                else
                    c--;
            }
        }
 
        // 사람 이동 & 최대 충전량 구하기
        x1 = 1, y1 = 1, x2 = 10, y2 = 10, total = 0;
        for (i = 0; i <= M; i++)
        {
            x1 += dir[user1[i]][0], y1 += dir[user1[i]][1];
            x2 += dir[user2[i]][0], y2 += dir[user2[i]][1];
            for (j = 1; j <= A; j++)
            {
                if (map[x1][y1][j] != 0)
                    BC1.push_back(j);
                if (map[x2][y2][j] != 0)
                    BC2.push_back(j);
            }
            if (BC1.empty())
                BC1.push_back(0);
            if (BC2.empty())
                BC2.push_back(0);
            len1 = BC1.size();
            len2 = BC2.size();
 
            MAX = 0;
 
            // 최대 충전량 구하기
            for (a = 0; a < len1; a++)
            {
                for (b = 0; b < len2; b++)
                {
                    result = 0;
                    if (BC1[a] == BC2[b])
                        result = map[x1][y1][BC1[a]];
                    else
                    {
                        result += map[x1][y1][BC1[a]];
                        result += map[x2][y2][BC2[b]];
                    }
                    if (MAX < result)
                        MAX = result;
                }
            }
 
            total += MAX;
 
            BC1.clear();
            BC2.clear();
        }
 
        cout << "#" << test_case << " " << total << endl;
    }
    return 0;
}

실행 결과