가장 차이가 적은 두 수를 고르는 문제 인데요...

  • canuyes
    canuyes

    우선 질문에 앞서 문제의 내용과 출처를 밝힙니다.
    http://www.acmicpc.net/problem/2230 입니다.

    답을 내는 알고리즘은 작성했지만, 시간 초과가 뜨네요...

    아래는 아주 나이브한 제 소스입니다.

    #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(void){
    long long i,j,temp,N,M,MIN=20000000000;
    vector<long long> arr;
    cin>>N>>M;
    for(i=0;i<N;i++){
              cin>>temp;
              arr.push_back(temp);
    }
    sort(arr.begin(),arr.end());
    for(i=0;i<N-1;i++){
              if(MIN==M){break;}
              else{
                  for(j=1;i+j<N;j++){
                              temp=arr[i+j]-arr[i];
                              if(temp>=M){
                                         if(MIN>temp){MIN=temp;}
                                         break;
                              }
                  }
                  if(i+j==N){break;}
              }
    }
    cout<<MIN<<endl;                 
    return 0;
}

    문제에 명시되어 있는 난이도도 쉬움이고 해서 만만하게 보았는데
    애를 먹고 있습니다.

    설마하는 마음에 분할정복 기법도 적용해 보았는데,
    왼쪽 수직선, 오른쪽 수직선, 양쪽을 가로지르는 수직선으로
    문제를 분할할 때, 양쪽을 가로지르는 수직선을 구현하지 못했습니다.

    이문제..어떻게 풀어야 하나요?ㅜ


    10년 전
9개의 댓글이 있습니다.
  • Pekaz
    Pekaz

    흠 일단은 그렇게 푸시면 시간복잡도가 O(N^2) 으로 시간초과가 납니다.
    N이 10만일때 2초를 그냥 넘어버리죠!
    문제를 푸는 힌트를 주자면 ..
    제가 직접 안풀어봐서 확신은 못하겠지만
    파라매트릭서치 라는 기법을 사용하면 풀수 있을것 같습니다.(찾아보시길!)
    더 자세한 설명이 필요하시면 한번더 댓글을 달아주세요~


    10년 전 link
  • Pekaz
    Pekaz

    그런데 분할정복 기법 설명하신건 제가 이해를 잘 못하겠네요 ㅠ 죄송


    10년 전 link
  • canuyes
    canuyes

    답변 감사합니다^^
    파라매트릭서치 검색해보겠습니다!


    10년 전 link
  • Pekaz
    Pekaz

    그런데 더 쉽게도 풀수 있군요 ㅠㅠ...


    10년 전 link
  • Pekaz
    Pekaz

    정렬을 하고나서 M차이가 나면 , M차이보다 더 큰건 볼필요가 없다는것에 입각해보시길 바랍니다 덜덜... 파라매트릭서치도 좋은 기법중 하나긴 한데 여기서 거기까지 쓸 필요가 없네요 ㅠㅠ 아 부끄


    10년 전 link
  • Kureyo
    Kureyo

    안녕하세요
    A배열은 정렬되어있다는 가정하에
    어떤 i에 대해, A[j]-A[i]>=M인 가장 작은 j를 안다고 합시다.
    이제 i+1에 대해 생각하면, k=j-1,j-2,j-3...에 대해서는 그 차이
    A[k]-A[i+1]가 M에 못미친다고 생각 할 수 있습니다.
    왜냐하면 A[i]<=A[i+1] 이고, A[k]-A[i]<M 이었기 때문에
    A[k]-A[i+1]<M이 성립하기 때문입니다.
    예를 들어 M = 999 이고 A = [1,3,5,....199999] 이라고 합시다
    A[0]=1이니까 A[500]=1001인 지점에서 차이가 최초로 M을 넘어갑니다
    이제 A[1]=3에 대해 할때 A[2..499]까지는 비교해볼 필요없이
    그 차이가 999에 못미친다는 것을 알 수 있습니다.
    주어진 코드는 최악의 경우 O(N^2)인데요, 이 방법을 쓰면 O(N)시간에 풀수 있습니다.


    10년 전 link
  • canuyes
    canuyes

    검색 해보았는데요.
    혹시 'M이상의 최소 차이'를 미리 정해두고
    그런 차이를 갖게하는 순서 쌍이 있나 찾아 보라는 말씀이신가요?


    10년 전 link
  • Pekaz
    Pekaz

    ㅠㅠ ㅋㅋ 좋은 설명을 구래요님이 달아주셨네여 ...


    10년 전 link
  • canuyes
    canuyes

    답변 정말 감사합니다!
    구현해보도록 하겠습니다. ㅜㅜ


    10년 전 link

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