[C++] SWEA 5644 - 무선 충전(2)

두 번째 풀이입니다. 예전과는 어떻게 얼마나 달라졌는지 궁금해서 한번 더 풀어보았습니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo&categoryId=AWXRDL1aeugDFAUo&categoryType=CODE&problemTitle=5644&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

<풀이>

1. 배터리 BC 정보와 사용자 이동 정보를 입력받는다.

2. 사용자가 충전한 양의 합의 최댓값을 출력한다.

 

<해법>

1. 사용자가 충전한 양의 합이 최대가 되는 BC 선택하기

=> 사용자 한명씩 모두 BC를 선택해보아야 합니다. 따라서, 저는 재귀함수를 이용해서 브루트포스를 구현하였습니다.

 

2. 구현 전 총정리

=> 아래는 구현 전 정리한 생각입니다.

(1) 주어진 사용자 이동 정보를 이용해 시뮬레이션을 진행한다.

(2) 사용자가 이동할 때마다, 재귀함수를 이용해 충전한 양의 최댓값을 구한다.

(3) 충전한 양의 합을 출력한다.

자세한 구현은 아래 코드를 참조해주세요.

 

#include <iostream>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
struct pos {
    int x, y;
};
 
struct bc {
    pos p;
    int c;
    int power;
};
 
int dx[] = { 0,-1,0,1,0 };
int dy[] = { 0,0,1,0,-1 };
 
int M, A;
int dir[2][101];
bc BC[8];
pos user[2];
bool visited[8];
int answer;
 
bool canCharge(pos p, int num) {
    if (abs(p.x - BC[num].p.x) + abs(p.y - BC[num].p.y) <= BC[num].c) return true;
    return false;
}
 
int chargeAmount(int idx) {
    if (idx == 2) return 0;
 
    int ret = 0;
    for (int i = 0; i < A; i++) {
        if (canCharge(user[idx], i) && !visited[i]) {
            visited[i] = true;
            ret = max(ret, chargeAmount(idx + 1) + BC[i].power);
            visited[i] = false;
        }
    }
    ret = max(ret, chargeAmount(idx + 1));
    return ret;
}
 
int simulation() {
    int output = 0;
    user[0].x = 1, user[0].y = 1, user[1].x = 10, user[1].y = 10;
    
    for (int time = 0; time <= M; time++) {
        for (int i = 0; i < 2; i++) {
            user[i].x += dx[dir[i][time]];
            user[i].y += dy[dir[i][time]];
        }
        output += chargeAmount(0);
    }
   
    return output;
}
 
void solution() {
    answer = simulation();
}
 
int main() {
    int test_case;
    int T;
    cin >> T;
    for (test_case = 1; test_case <= T; test_case++) {
        //초기화
        M = 0, A = 0;
        memset(dir, 0, sizeof(dir));
        for (int i = 0; i < 8; i++) {
            BC[i] = { 0,0,0,0 };
        }
        for (int i = 0; i < 2; i++) {
            user[i] = { 0,0 };
        }
        memset(visited, false, sizeof(visited));
        answer = 0;
 
        //입력
        cin >> M >> A;
        for (int i = 0; i < 2; i++) {
            for (int j = 1; j <= M; j++) {
                cin >> dir[i][j];
            }
        }
        for (int i = 0; i < A; i++) {
            int x = 0, y = 0, c = 0, power = 0;
            cin >> y >> x >> c >> power;
            BC[i] = { {x,y},c,power };
        }
 
        //해법
        solution();
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
    //종료
    return 0;
}

 

시뮬레이션과 DFS에 대해 알아볼 수 있는 문제였습니다.