DARPA문제에서 완전탐색으로 모든 경우의 수를 따지면서 푸는 답안을 만들었습니다.

1. 항상 가장 멀리떨어진 것이 답이니 맨 처음과 맨 뒤를 먼저 선택했습니다.

2. 오름차순으로 정렬된 모든 경우의 수를 탐색합니다.

picked[] 배열을 만들어서 지금 까지 고른 것을 저장하고,
- upperIndex : i번째를 골랐다면 그보다 바로 위에 선택된 것
- lowerIndex : i번째를 골랐다면 그보다 바로 아래 선택된 것

그래서 i번째와 upper , lower사이의 거리중 짧은 것을 선택합니다.
이런 과정을 모든 선택되지 않은 곳에 애해 반복해서 가장 거리가 멀리 떨어져있는 것을 고릅니다.

이렇게 풀었는데 계속 오답이 나옵니다. 이유를 알 수 있을까요?

~~~ c++
#include
#include
#include
#include
#include
#include

using namespace std;

int n,m;
double dist[200];
bool picked[200];

double darpa();
int getUpperIndex(int index);
int getLowerIndex(int index);
int main(int argc, char const *argv[])
{
int c;
cin>>c;
while(c--){
memset(picked, 0, sizeof(picked));
cin>>n>>m;
for(int i=0; i cin>>dist[i];
}
sort(dist, dist+m);

    double ret=darpa();
    ret=round(ret *100.00) /100.00;
    cout<<fixed << setprecision(2);
    cout<<ret<<endl;
}
return 0;

}

double darpa(){

picked[0]=true;
picked[m-1]=true;
double maximum=dist[m-1]-dist[0];
for(int left=n-2; left>0; left--){
    double val=0;
     int index=-1;
    for(int i=0; i<m ; i++){
        if(picked[i]) continue;
        int lowerIndex=getLowerIndex(i);
        int upperIndex=getUpperIndex(i);
        double cand=min(dist[i]-dist[lowerIndex], dist[upperIndex]-dist[i]);
        if(val <= cand){
            val=cand;
            index=i;
        }
    }
    maximum=min(maximum, val);
    picked[index]=true;
}

return maximum;

}

int getLowerIndex(int index){
for(int i=index-1; i>=0; --i){
if(picked[i]){
return i;
}
}
}

int getUpperIndex(int index){
for(int i=index+1; i<m; ++i){
if(picked[i]){
return i;
}
}

}
~~~