algospot DARPA

문제 링크입니다: https://algospot.com/judge/problem/read/DARPA

답이 자연수로 표현 가능하더라도 소수 둘째자리까지 표현하는 것이 포인트이기 때문에 iomanip 헤더파일을 추가하고

cout << fixed << setprecision(2)를 추가해주는 것이 중요했습니다.

/*

DARPA Grand Challenge 는 운전자 없는 차들을 컴퓨터 인공지능으로 조작해 누가 먼저 결승점에 도달하느냐를 가지고 겨루는 인공지능 대회입니다.

2004년 DARPA Grand Challenge 의 과제는 사막을 가로지르는 240km 도로를 완주하는 것이었습니다.

우리는 이 경기를 N 개의 카메라로 중계하려고 합니다.

이 도로에는 카메라를 설치할 수 있는 곳이 M 군데 있습니다.

여기에 카메라를 배치하여, 가장 가까운 두 카메라 간의 간격을 최대화하고 싶습니다.

이와 같은 배치를 찾아내는 프로그램을 작성하세요.

*/

#include <iostream>

#include <vector>

#include <algorithm>

#include <iomanip>

using namespace std;

 

int cameraNum, installNum; //카메라 갯수와 설치 가능 갯수

 

//결정 문제: 정렬되어 있는 locations 중 cameras를 선택해 모든 카메라 간의 간격이

//gap 이상이 되는 방법이 있는지 반환

bool decision(const vector<double> &location, int cameras, double gap)

{

        //카메라를 설치할 수 있을 때마다 설치하는 탐욕적 알고리즘

        double limit = -1;

        int installed = 0;

        for (int i = 0; i < location.size(); i++)

        {

               if (limit <= location[i])

               {

                       ++installed;

                       //location[i]+gap 이후는 되어야 카메라 설치 가능

                       limit = location[i] + gap;

               }

        }

        //결과적으로 cameras대 이상을 설치할 수 있었으면 성공

        return installed >= cameras;

}

 

//최적화 문제: 정렬되어 있는 locations 중 cameras를 선택해 최소 간격을 최대화

double optimize(const vector<double> &location, int cameras)

{

        double low = 0, high = 241;

        //반복문 불변식:decision(low) && !decision(high)

        for (int i = 0; i < 100; i++)

        {

               double mid = (low + high) / 2.0;

               //간격이 mid 이상이 되도록 할 수 있으면 답은 [mid, hi]에 있다

               if (decision(location, cameras, mid))

                       low = mid;

               else

                       high = mid;

        }

        return low;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 1 || test_case>50)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               vector<double> location;

               cin >> cameraNum >> installNum;

 

               for (int j = 0; j < installNum; j++)

               {

                       double coord;

                       cin >> coord;

                       location.push_back(coord);

               }

               sort(location.begin(), location.end());

               cout << fixed << setprecision(2);

               cout << optimize(location, cameraNum) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략