[ SWEA ] 5644. 무선 충전

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

SW Expert Academy

풀이 방법

각 사람으로부터 모든 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를 더하여 반환한다.

 

전체 코드는 여기서 확인할 수 있다.