Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- C++
- Application Layer
- DB
- boot sequence
- 관계형 모델
- ps
- 백준
- 문제풀이
- 프로그래머스
- 응용 계층
- 임베디드
- STL
- baekjoon
- 네트워크
- Network
- Djikstra
- Embedded
- swea
- dp
- BHS
- 다익스트라
- Database
- leetcode
- 릿코드
- 부트시퀀스
- 전송 계층
- 자료구조
- BST
- 데이터베이스
- Transport layer
Archives
- Today
- Total
BOBO's Note
[ SWEA ] 5644. 무선 충전 본문
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo
풀이 방법
각 사람으로부터 모든 BC(=Battery Charger)까지의 거리를 계산하여 선택할 수 있는 BC를 available_bc 벡터에 추가한다.
for (int i = 0; i < 2; i++) {
for (int j = 0; j < num_bc; j++) {
d = abs(people[i].r - bc[j].r) + abs(people[i].c - bc[j].c);
if (d <= bc[j].range) {
available_bc[i].push_back(j);
}
}
}
그 후, choose_bc() 함수를 통해 모든 BC 선택 조합을 구하여 choose 벡터에 추가하고, 그 중 최대로 충전할 수 있는 양을 구한다.
void choose_bc(int n) {
if (n == 2) {
max_charge_sum = max(max_charge_sum, charge());
return;
}
int size = available_bc[n].size();
if (size == 0) choose_bc(n + 1);
else {
for (int i = 0; i < size; i++) {
choose.push_back(available_bc[n][i]);
choose_bc(n + 1);
choose.pop_back();
}
}
}
charge() 함수는 두 사람이 선택한 BC가 주어졌을 때, 그 때의 두 사람의 충전량을 반환하는 함수이다.
int charge() {
if (choose.size() == 0) return 0;
else if (choose.size() == 1 || choose[0] == choose[1])
return bc[choose[0]].power;
else return bc[choose[0]].power + bc[choose[1]].power;
}
만약 둘 다 선택할 수 없는 BC가 없을 때에는 0을 반환한다.
그리고 둘 중 하나만 BC를 선택할 수 있거나 두 사람이 같은 BC를 선택한 경우에는 선택된 BC의 power를 반환한다. 두 사람이 같은 BC를 선택했을 때 각 사람은 power/2을 충전할 수 있기 때문에 전체 충전량은 power이다.
마지막으로 선택한 BC가 다를 때, 그 두 BC의 power를 더하여 반환한다.
전체 코드는 여기서 확인할 수 있다.
'Algorithm > Problem Solving' 카테고리의 다른 글
[ LeetCode ] 480. Sliding Window Median (0) | 2020.06.24 |
---|---|
[ Baekjoon ] 2110. 공유기 설치 (0) | 2020.06.24 |
[ SWEA ] 5658. 보물상자 비밀번호 (0) | 2020.06.06 |
[ SWEA ] 5656. 벽돌 깨기 (0) | 2020.06.06 |
[ SWEA ] 2383. 점심 식사시간 (0) | 2020.06.06 |
Comments