문제 링크
https://www.acmicpc.net/problem/11663
문제
일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.
출력
입력으로 주어진 각각의 선분 마다, 선분 위에 입력으로 주어진 점이 몇 개 있는지 출력한다.
예제 입력 1
5 5
1 3 10 20 30
1 10
20 60
3 30
2 15
4 8
예제 출력 1
3
2
4
2
0
알고리즘 분류
- 이분 탐색
풀이
C++에서는 이분 탐색 함수 lower_bound(), upper_bound()가 존재한다.
lower_bound()는 매개 변수가 되는 수와 같거나 큰 숫자 중 가장 작은 수의 index를, upper_bound()는 매개 변수가 되는 수보다 큰 숫자 중 가장 작은 수의 index를 반환한다.
선분의 시작점과 값이 같거나, 큰 숫자 중 가장 작은 수의 index i를 구한다.(lower_bound)
선분의 끝점보다 큰 숫자 중 가장 작은 수의 index j를 구한다.(upper_bound) 이는 i번째부터 j번째까지의 개수를 구할 때 j에서 i를 빼고 1을 더하는 것처럼, 끝점 다음 점의 index인 j에서 i를 빼면 선분에 포함된 점의 개수를 구할 수 있다.
코드
더보기
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define INF 1000000001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
using namespace std;
int N, M, S, E;
vector<int> Points;
void input() {
cin >> N >> M;
Points.resize(N + 1);
for (int i = 0; i < N; i++) {
cin >> Points[i];
}
Points[N] = INF;
sort(Points.begin(), Points.end());
while (M--) {
cin >> S >> E;
int L = lower_bound(Points.begin(), Points.end(), S) - Points.begin();
int R = upper_bound(Points.begin(), Points.end(), E) - Points.begin();
cout << R - L << "\n";
};
}
int main() {
FASTIO
input();
return 0;
}
'BOJ > Silver' 카테고리의 다른 글
[BOJ/Silver 1] 백준 14426 접두사 찾기(C++) (2) | 2024.09.24 |
---|---|
[BOJ/Silver 1] 백준 29634 Hotel(C++) (3) | 2024.09.23 |
[BOJ/Silver 2] 백준 11568 민균이의 계략(C++) (2) | 2024.07.14 |
[BOJ/Silver 2] 백준 14430 자원 캐기(C++) (0) | 2024.07.11 |
[BOJ/Silver 3] 백준 31869 선배님 밥 사주세요!(C++) (0) | 2024.07.10 |