[Algospot] DARPA Grand Challenge (문제 ID : DARPA)

문제

DARPA Grand Challenge 는 운전자 없는 차들을 컴퓨터 인공지능으로 조작해 누가 먼저 결승점에 도달하느냐를 가지고 겨루는 인공지능 대회입니다. 2004년 DARPA Grand Challenge 의 과제는 사막을 가로지르는 240km 도로를 완주하는 것이었습니다.

우리는 이 경기를 N 개의 카메라로 중계하려고 합니다. 이 도로에는 카메라를 설치할 수 있는 곳이 M 군데 있습니다. 여기에 카메라를 배치하여, 가장 가까운 두 카메라 간의 간격을 최대화하고 싶습니다. 이와 같은 배치를 찾아내는 프로그램을 작성하세요.

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 이 주어집니다. 각 테스트 케이스의 첫 줄에는 카메라의 개수 N (<= 100) 과 설치 가능한 중계소의 수 M (N <= M <= 200) 이 주어집니다. 그 다음 줄에는 M 개의 실수로, 카메라를 설치 가능한 곳의 위치가 오름 차순으로 주어집니다. 각 위치는 시작점에서부터의 거리로, 240 이하의 실수이며 소숫점 둘째 자리까지 주어질 수 있습니다.

 

출력

각 테스트 케이스마다 가장 가까운 두 카메라 간의 최대 간격을 소수점 셋째 자리에서 반올림해 출력합니다.

---

최적화와 결정 문제이다. 

최적화와 결정 알고리즘은 optimize() 와 decision()으로 구성된다. optimize는 문제가 요구하는 답을 찾는 함수이고, decision은 특정 값에 대해 그 값으로 답이 가능한지 불가능한지 여부를 반환한다. 

이 문제에서는 optimize(camera) = 카메라 간 최소 간격의 최대치를 반환.

decision(camera, gap) = 모든 카메라를 적절히 배치해 간격을 gap 이상으로 하는 방법이 있는가를 반환한다.

이 두 함수를 적절히 설계하면 답을 구할 수 있다. 

 

optimize에서 최적화 된 간격을 구하기 위해  이분 탐색을 사용하는걸 확인하자.

 

그리고 또 하나, 답을 소수점 둘째자리까지 고정해서 출력을 해야하는데 이를 위해 <iomanip> 헤더를 포함하고

답을 출력하기 전에 cout << fixed << setprecision(2) 을 통해 부동소수점을 고정해야한다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/DARPA.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;

int C, N, M;
vector<double> location;

bool decision(int camera, double gap)
{
	double limit = -1;
	int install = 0;
	for (int i = 0; i < location.size(); i++) {
		if (limit <= location[i]) {
			++install;
			limit = location[i] + gap;
		}
	}
	return install >= camera;
}

double optimize(int camera)
{
	double lo = 0.0, hi = 241.0;
	for(int it = 0;it<100;it++){
		double mid = (lo + hi) / 2.0;
		if (decision(camera, mid))
			lo = mid;
		else
			hi = mid;
	}
	return lo;
}

int main()
{
	cin >> C;
	while (C--) {
		location.clear();
		cin >> N >> M;
		for (int i = 0; i < M; i++) {
			double num;
			cin >> num;
			location.push_back(num);
		}
		cout << fixed << setprecision(2);
		cout << optimize(N) << endl;
	}
}