algospot DARPA DARPA Grand Challenge

문제

https://algospot.com/judge/problem/read/DARPA

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

// 결정 문제
bool decision(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++;
            limit = location[i] + gap;
        }
    }
    return installed >= cameras;
}

// 최적화 문제
double optimize(vector<double>& location, int cameras){
    double left = 0, right = 241;
    for(int it = 0; it < 100; it++){
        double mid = (left+right)/2.0;
        // m개의 카메라 중 가장 가까운 두 카메라의
        // 간격이 mid(gap)혹은 그 이상인 배치가
        // 있는지 확인한다.
        if(decision(location, cameras, mid))
            left = mid;
        else
            right = mid;
    }
    return left;
}

int main(){
    int tc;
    scanf("%d", &tc);
    while(tc--){
        int n, m;
        double tmp;
        cin >> n >> m;
        vector<double> location(m);
        for(int i = 0; i < m; i++)
            scanf("%lf", &location[i]);
        printf("%.2lf\n", optimize(location, n));
    }
    return 0;
}

종만북 "최적화 문제 결정 문제로 바꿔 풀기" 단원의 예제 문제이다.

같은 유형의 쉬운 문제들을 풀어봤기 때문에 쉽게 접근할 수 있을꺼라 생각했지만 생각보다 어려웠고 결국 풀이를 보게 되었다.

여차저차해서 코드를 이해하고 문제를 풀긴 했지만, 결정 문제를 풀기 위한 알고리즘 선택에서 탐욕법을 떠올리는 과정의 설명이 잘 이해가 되질 않는다. 제일 중요한 걸 놓친 기분이다.