[BOJ/백준][Gold5] 2230 : 수 고르기 (C++)

https://www.acmicpc.net/problem/2230

2230번: 수 고르기

 

 

[난이도] Gold5
[유형] 이분탐색

[풀이]
N<=100000 이므로 N^2개의 모든수의 짝을 구해보기엔 시간이 오래걸리므로
이분탐색을 이용하였습니다.
배열 A를 정렬시킨 뒤,
A[i] (i:0~N-1)를 고정시키고 A[i]~A[N-1] 의 숫자 중 조건을 가장 잘 만족시키는
숫자 A[j]를 찾으면 됩니다.
A[j]-A[i] >= M 이 조건이므로 A[i]~A[N-1]의 숫자 A[j] 중 A[j] >= A[i]+M 을 만족하는
j를 lower_bound를 이용해 찾을 수 있습니다.

아래 코드와 같이 lower_bound(a+i,a+N,a[i]+M) 는 a[i]+M 이상인 최솟값의 iterator를 반환하므로
(반환된 iterator:it)-A 의 값이 곧 index j의 값이 됩니다.
A[j]-A[i]는 정답의 후보가 될 수 있으므로 ans 값을 업데이트 해주면 됩니다.

 

#include <algorithm>
#include <cstdio>
using namespace std;
using ll = long long;
int N;
ll M,a[100001];
int main(){
    scanf("%d%lld",&N,&M);
    for(int i=0;i<N;i++) scanf("%lld",&a[i]);
    sort(a,a+N);
    int ans = 2e9;
    for(int i=0;i<N;i++){
        int idx = lower_bound(a+i,a+N,a[i]+M)-a;
        if(idx<N) ans = min(int(a[idx]-a[i]),ans);
    }
    printf("%d",ans);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2230.cpp