DARPA 문제 질문입니다. 액땜 DARPA문제에서 완전탐색으로 모든 경우의 수를 따지면서 푸는 답안을 만들었습니다. 항상 가장 멀리떨어진 것이 답이니 맨 처음과 맨 뒤를 먼저 선택했습니다. 오름차순으로 정렬된 모든 경우의 수를 탐색합니다. 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일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
액땜
DARPA문제에서 완전탐색으로 모든 경우의 수를 따지면서 푸는 답안을 만들었습니다.
항상 가장 멀리떨어진 것이 답이니 맨 처음과 맨 뒤를 먼저 선택했습니다.
오름차순으로 정렬된 모든 경우의 수를 탐색합니다.
picked[] 배열을 만들어서 지금 까지 고른 것을 저장하고,
lowerIndex : i번째를 골랐다면 그보다 바로 아래 선택된 것
그래서 i번째와 upper , lower사이의 거리중 짧은 것을 선택합니다.
이런 과정을 모든 선택되지 않은 곳에 애해 반복해서 가장 거리가 멀리 떨어져있는 것을 고릅니다.
이렇게 풀었는데 계속 오답이 나옵니다. 이유를 알 수 있을까요?
3년 전