[algospot] DARPA

문제링크 입니다

[DARPA] 문제 😄😄😄😄😄

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

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

[풀이]

카메라를 놓을 수 있는지 없는지를 반환하는 decision(locations, cameras, gap) 을 구현하여 0점과 가장 멀리(GAP을 최대화하는)에 처음 카메라를 둘 수 있는 위치를 찾고 두고 GAP을 찾는다.

이를 이분법을 사용해 검색 수를 줄인다.

입력

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

출력

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

입력 예제

3
2 4
80 100 120 140
4 4
80 100 120 140.00
4 7
0 70 90 120 200 210 220

출력 예제

60.00
20.00
50.00

전체 코드는 다음과 같습니다.

//
//  DARPA.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/11/03.
//

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

ifstream fin("DARPA.txt");

int n; // 카메라의 개수
int m; // 설치 가능한 중계소의 수
int min_distance;
bool solution(const vector<double> &locations, int cameras, double gap){
    double limit = -1;
    int installed = 0;
    for(int i=0; i<locations.size(); i++){
        if(limit <= locations[i]){
            installed++;
            limit = locations[i] + gap;
        }
    }
    return installed >=cameras;
}
double optimize(const vector<double> &locations, int cameras){
    double lo=0, hi = 241;
    for(int i=0; i<100; i++){
        double mid = (lo+hi)/2.0;
        if(solution(locations,cameras,mid)){
            lo = mid;
        }
        else{
            hi = mid;
        }
    }
    return lo;
}
int main(){
    int test_case;
    fin >> test_case;
    for(int test=0; test < test_case; test++){
        fin >> n >> m;
        vector<double> locations;
        for(int i = 0; i<m; i++){
            double location;
            fin >> location;
            locations.push_back(location);
        }
        printf("%0.2f\n",optimize(locations,n));

    }
}