[백준 2230번] 수 고르기

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

2230번: 수 고르기

---

수 고르기 문제는 이분탐색을 이용하여 해결할 수 있습니다. 

먼저, 수열의 임의의 요소 X를 선택하고 X + m보다 크거나 같은 값 중 가장 작은 값을 Y라고 하면, Y - X의 최솟값을 찾으면 됩니다. 

이 값을 찾기 위해 이분탐색이 사용됩니다.

lower_bound(first, last, value)는 value보다 크거나 같은 값들 중 제일 작은 값을 찾는데 사용됩니다. 

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int arr[100010];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> arr[i];

    sort(arr, arr + n); // 오름차순으로 정렬

    int MAX = INT_MAX;
    for(int i = 0; i < n - 1; i++){ // arr[i]를 선택
        int idx = lower_bound(arr + i,  arr + n, arr[i] + m) - arr; // arr[i] + m보다 크거나 같은 값 중 가장 작은 값을 찾음
        if(idx < n) MAX = min(MAX, arr[idx] - arr[i]);  // arr[i] + m보다 작거나 같은 수가 존재한다면, 기존 m값과 비교하여 더 작은 수를 저장
    }
    cout << MAX;
}