[백준 11663번] 선분 위의 점 (C++)

문제링크 : https://www.acmicpc.net/problem/11663

11663번: 선분 위의 점

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, arr[100001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr, arr+N);

    for(int i=0; i<M; i++)
    {
        int x, y;
        cin >> x >> y;
        int front = lower_bound(arr, arr+N, x)-arr; //x이상의 값이 처음 나오는 위치
        int end = upper_bound(arr, arr+N, y)-arr; //y초과의 값이 처음 나오는 위치
        cout << end - front <<"\n";
    }

    return 0;
}

lower_bound 함수와 upper_bound 함수를 사용하여 쉽게 풀 수 있는 문제다.

lower_bound 함수는 해당 값이상의 값이 처음 나오는 위치를 반환해주고,

upper_bound 함수는 해당 값을 초과하는 값이 처음 나오는 위치를 반환해준다.  

 

따라서 upper_bound를 통해 얻은 위치 - lower_bound 함수를 통해 얻은 위치를 해주면 쉽게 사이에 있는 값의 갯수를 알 수 있다.

5 5
1 3 10 20 30
1 10
20 60
3 30
2 15
4 8

x = 1, y = 10의 경우
x = 1이상인 값 (1)의 위치 0
y 초과하는 값 (20)의 위치 3

3 - 0 = 3 (1, 3, 10)

 

해당 함수들을 사용하기 위해선 정렬이 필요하므로 입력받은 arr 배열을 꼭 정렬해주어야 한다.