[SWEA] 5644. 무선 충전

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

SW Expert Academy

 

문제 이해

0초부터 M초까지 이동하면서 해당 위치에서 두 사람이 충전할 수 있는 최댓값을 구해서 더해주면 된다. 

문제 이해는 어렵지 않지만, 가능한 최대 충전값을 찾는 게 좀 까다롭다. 

 

나는 decide라는 함수를 만들어서 특정 시간에서 A와 B가 충전할 수 있는 최댓값을 반환하도록 했다. 

우선 각 충전소를 보면서 A, B와의 거리가 그 충전소의 충전범위 내인지를 확인하여, acan, bcan이라는 배열에 저장한다.

acan과 bcan 은 i번째 충전소에서 A가 혹은 B가 충전할 수 있는지를 true/false로 저장하는 배열이다.

 

그런 후에 A와 B가 충전소를 하나씩 고를 수 있는 모든 경우 (충전소 개수 * 충전소 개수)를 살핀다.

여기서 둘이 같은 충전소를 선택한 경우와 그렇지 않은 경우로 나눈다.

 

둘이 같은 충전기를 선택한 경우에, 만약 둘 중 하나 혹은 둘 다가 그 충전소에서 충전할 수 있으면, 그 충전소의 충전량(p)이 e가 된다. (e: 최대 충전량이 될 후보 충전량)

• 그 충전기에서 한명만 충전할 수 있는 경우: e = p
• 그 충전기에서 둘 다 충전할 수 있는 경우, 그리고 그러려는 경우: e = p/2 + p/2
• 결국 둘다 그 충전소를 선택했으면 둘 다 충전이 가능하든, 한 명만 가능하든  e = p이다

둘이 다른 충전기를 선택한 경우, 각자 충전 가능하면 충전하고 아님 말고이다.

여기서 그냥 acan 혹은 bcan의 값 (0 or 1)을 곱한 값을 더해서 if문으로 분기하지 않았다.

 

작성 코드

#include <stdio.h>
#define ABS(x) (((x)>0) ? (x) : -(x))

int M, A; // 이동 시간, 충전기의 개수
int dirA[100+10]; // A의 이동 정보
int dirB[100+10]; // B의 이동 정보

int curyA, curxA;
int curyB, curxB;
int power = 0;
typedef struct BC{
    int y;
    int x;
    int c;
    int p;
}BC;
BC Clist[8+2]; // 충전기 개수

// 방향 벡터
int dy[] = {0, -1, 0, 1, 0}; // X상우하좌
int dx[] = {0, 0, 1, 0, -1};

int decide(int ay, int ax, int by, int bx){
    // 현재 위치에서 충전할 수 있는 최대
    int acan[8] = {0, };
    int bcan[8] = {0, };
    int acnt = 0, bcnt = 0;
    int d;
    int maxe = 0;
    int e = 0;

    // 충전 가능한 충전소 찾기 
    for(int i = 0; i<A; i++){
        d = ABS(Clist[i].y - ay) + ABS(Clist[i].x - ax);
        if(d <= Clist[i].c) {
            acan[i] = 1;
            acnt++;
        }
        d = ABS(Clist[i].y - by) + ABS(Clist[i].x - bx);
        if(d <= Clist[i].c) {
            bcan[i] = 1;
            bcnt++;
        }
    }

// 충전이 가능하다면 가능한 최대 찾기

    for(int i = 0; i<A; i++){
        for(int j = 0; j<A; j++){
            // A는 i번째 충전기, B는 j번째 충전기
            if(i == j){
                // 둘이 같은 충전기에서 충전하려 함
                if(acan[i] + bcan[j] >= 1){ // 그리고 둘다 가능 or 둘 중 하나 가능
                    e = Clist[i].p;
                    if(maxe < e) maxe = e;
                }
            }
            else{
                // 둘이 다른 충전기
                e = Clist[i].p * acan[i] + Clist[j].p * bcan[j];
                if(maxe < e) maxe = e;
            }
        }
    }
    return maxe;

}

void getInput(void){

    scanf("%d %d", &M, &A);
    // 사용자 정보 받기
    for(int i = 1; i<=M; i++){
        scanf("%d", &dirA[i]);
    }
    for(int i = 1; i<=M; i++){
        scanf("%d", &dirB[i]);
    }
    // 충전기 정보 받기
    for(int i = 0; i<A; i++){
        scanf("%d %d %d %d", &Clist[i].x, &Clist[i].y, &Clist[i].c, &Clist[i].p);
    }
}

int main(void){
    int T;
    scanf("%d", &T);
    for(int t= 0; t<T; t++){
        // 각 테스트 케이스
        getInput();
        curxA = 1, curyA = 1;
        curxB = 10; curyB = 10;
        power = 0;
        // 이동하면서, 충전가능하면 충전해보자
        
        for(int i = 0; i<=M; i++){
            curyA += dy[dirA[i]];
            curxA += dx[dirA[i]];
            curyB += dy[dirB[i]];
            curxB += dx[dirB[i]];

            power += decide(curyA, curxA, curyB, curxB);

        }

        printf("#%d %d\n", t+1, power);
    }
    return 0;
}