DARPA 문제 질문입니다.

  • 액땜
    액땜

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

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

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

    picked[] 배열을 만들어서 지금 까지 고른 것을 저장하고,

    • upperIndex : i번째를 골랐다면 그보다 바로 위에 선택된 것
    • lowerIndex : i번째를 골랐다면 그보다 바로 아래 선택된 것

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

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

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <cmath>
    #include <iomanip>
    
    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<m; 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;
            }
        }
    
    }
    


    3년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.