5644. [모의 SW 역량테스트] 무선 충전

[URL]

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

SW Expert Academy

[풀이 과정]

시뮬레이션

중복 순열 (user가 2명 뿐이라 2중 for문으로 구현)

 

1. 초기화

2. 입력

3.

각 BC (Battery Charger)의 범위이면 map[i][j]++;

이유: 각 uesr의 가능한 bc의 개수를 찾기위함

 

또한, 각 BC영역을 vector bcArea[]에 (x,y)형태로 저장하였다. 

이유: 중복 순열 시 최대값을 계산하기 위함

 

4. 출발점 sum에 더해준다.

각 for문을 돌면 sum에 최대값(getMax) 더해주면 끝

 

[소스 코드]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
using namespace std;
 
struct BC {
    int x;
    int y;
    int coverage;
    int performance;
};
 
struct info {
    int x;
    int y;
};
 
vector <info> bcArea[8];
 
int M;
int A;
int moveA[100];
int moveB[100];
 
int map[11][11];
BC bc[8];
 
int candA[8];
int candB[8];
 
 
int getMax(int ax, int ay, int bx, int by) {
    int max = 0;
 
    int possibleA = map[ax][ay];    // 가능한 A의 개수
    int possibleB = map[bx][by];    // 가능한 B의 개수
 
    int aCnt = 0;
    for (int a = 0; a < A; a++)
    {
        for (int i = 0; i < bcArea[a].size(); i++)
        {
            if (bcArea[a][i].x == ax && bcArea[a][i].y == ay)
            {
                candA[aCnt] = a;
                aCnt++;
                break;
            }
        }
    }
 
    int bCnt = 0;
    for (int a = 0; a < A; a++)
    {
        for (int i = 0; i < bcArea[a].size(); i++)
        {
            if (bcArea[a][i].x == bx && bcArea[a][i].y == by)
            {
                candB[bCnt] = a;
                bCnt++;
                break;
            }
        }
    }
 
    if (possibleA >= 1 && possibleB >= 1)
    {
        for (int i = 0; i < possibleA; i++)    // A관리
        {
            for (int j = 0; j < possibleB; j++)    // B관리
            {
                int tempCal = 0;
                // 만약 candA[i] == candB[j] 같다면 -> res는 반값 계산
                if (candA[i] == candB[j])
                {
                    tempCal = bc[candA[i]].performance;
                }
                else
                {
                    tempCal = bc[candA[i]].performance + bc[candB[j]].performance;
                }
 
                if (tempCal >= max)
                    max = tempCal;
            }
        }
    }
    else
    {
        if (possibleA == 0)
        {
            int tempCal = 0;
 
            for (int j = 0; j < possibleB; j++)    // B관리
            {
                tempCal = bc[candB[j]].performance;
 
                if (tempCal >= max)
                    max = tempCal;
            }
        }
 
        if (possibleB == 0)
        {
            int tempCal = 0;
 
            for (int i = 0; i < possibleA; i++)    // A관리
            {
                tempCal = bc[candA[i]].performance;
 
                if (tempCal >= max)
                    max = tempCal;
            }
        }
    }
 
    return max;
}
 
void init() {
    // 초기화
    for (int i = 0; i < 8; i++)
    {
        bcArea[i].clear();
        candA[i] = 0;
        candB[i] = 0;
    }
    // map 초기화
    for (int i = 0; i < 11; i++) { memset(map[i], 0, sizeof(int) * 11); }
}
 
void input() {
    scanf("%d %d", &M, &A);
 
    // moveA, moveB 입력
    for (int m = 0; m < M; m++) { scanf("%d", &moveA[m]); }
    for (int m = 0; m < M; m++) { scanf("%d", &moveB[m]); }
 
    // 구조체 형태로 입력받고, bc배열 구조체 형태로 저장
    for (int a = 0; a < A; a++)
    {
        BC temp;
        scanf("%d %d %d %d", &temp.y, &temp.x, &temp.coverage, &temp.performance);
 
        bc[a] = temp;
    }
}
 
int main() {
    int T;
    scanf("%d", &T);
    for (int tc = 0; tc < T; tc++)
    {
        int sum = 0;
 
        init();
        input();
 
        for (int a = 0; a < A; a++)
        {
            for (int i = 1; i < 11; i++)
            {
                for (int j = 1; j < 11; j++)
                {
                    // 거리가 coverage 범위값이면 map[i][j]++;, bcArea[]에 (x, y)형태로 푸쉬
                    if (abs(bc[a].x - i) + abs(bc[a].y - j) <= bc[a].coverage)
                    {
                        map[i][j]++;
 
                        info temp;
                        temp.x = i;
                        temp.y = j;
 
                        bcArea[a].push_back(temp);
                    }
                }
            }
        }
 
        info userA;
        userA.x = 1;
        userA.y = 1;
 
        info userB;
        userB.x = 10;
        userB.y = 10;
 
        // 출발점 계산 : 0초 일때
        sum += getMax(userA.x, userA.y, userB.x, userB.y);
 
        for (int m = 0; m < M; m++)
        {
            // A, B 시작점에서 움직이기 시작
            // 1상 2우 3하 4좌
            if (moveA[m] == 1) { userA.x--; }
            else if (moveA[m] == 2) { userA.y++; }
            else if (moveA[m] == 3) { userA.x++; }
            else if (moveA[m] == 4) { userA.y--; }
 
            if (moveB[m] == 1) { userB.x--; }
            else if (moveB[m] == 2) { userB.y++; }
            else if (moveB[m] == 3) { userB.x++; }
            else if (moveB[m] == 4) { userB.y--; }
 
            // 매초마다 계산: M번
            sum += getMax(userA.x, userA.y, userB.x, userB.y);
        }
 
        printf("#%d %d\n", tc + 1, sum);
    }
 
    return 0;
}