[BOJ / C++] 2230 수 고르기

문제링크

문제
N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.

예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M = 3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.

입력
첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다.

출력
첫째 줄에 M 이상이면서 가장 작은 차이를 출력한다. 항상 차이가 M이상인 두 수를 고를 수 있다.

제한
1 ≤ N ≤ 100,000
0 ≤ M ≤ 2,000,000,000
0 ≤ |A[i]| ≤ 1,000,000,000

예제 입력 1
3 3
1
5
3
예제 출력 1
4

문제 정리

수 고르기 문제는 투 포인터와 이분 탐색으로 풀 수 있다. 그 중에서 이분 탐색으로 풀어보려한다. 이분 탐색 풀이를 생각하는건 조금 어렵다고 생각한다. 우선 i < j 이고 차이를 M이라고 했을 때

A[j]-A[i] >= M 이면서 A[j]-A[i]가 최소가 되는 경우를 구해야 한다.

위 내용을 A[j] >= A[i] + M을 이면서 A[j]가 최소가 되는 경우를 구한다와 같이 바꿀 수 있다.

-> A[i] + M보다 크거나 같은 값 중 가장 작은 값을 배열에서 찾는다. 이분 탐색의 lower_bound를 활용할 수 있다.

이분 탐색 알고리즘

구현 코드

#include <bits/stdc++.h>

using namespace std;

long A[100001];

int main()
{
    int n,m;
    cin >> n >> m;

    for(int i=0; i<n; i++)
        cin >> A[i];
    //이분 탐색을 위해 정렬한다
    sort(A,A+n);

    long min=2000000001;
    
    for(int i=0; i<n; i++)
    {   
    	//A[i]+m보다 크거나 같은 값 중 가장 작은 값의 인덱스를 구한다.
        int tmp = lower_bound(A, A+n, A[i]+m)- A;
        
        //차이가 m이상인지, 최소가 되는지를 확인
        if(A[tmp]-A[i]<min && A[tmp]-A[i]>=m)
            min=A[tmp]-A[i];
           
    }
    cout << min;
}

식을 바꾸고 lower_bound를 사용해야하는것을 생각해야한다는 점이 어려웠다. 크거나 같은 값 중 최솟값을 찾는 문제는 이분탐색으로 해결할 수 있다는 것을 기억해야겠다.