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

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

일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N, M ≤ 100,000
• 1 ≤ 입력으로 주어지는 모든 좌표 ≤ 1,000,000,000

 

아래 링크에 적어둔 upper_bound()와 lower_bound()를 사용해 답을 구할 수 있다. 해당 함수들을 사용하려면 탐색 대상이 되는 배열을 오름차순으로 정렬해야 한다는 것만 주의하면 된다.

[백준] 17124 - 두 개의 배열 (C++)

 

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, M, 점 정보 입력받기
2. 선분 정보를 입력받으면서 upper_bound()와 lower_bound() 함수로 선분 위에 있는 점의 개수 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n,m,dot[100001],x,y;

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

    cin >> n >> m;
    for (int i=0; i<n; i++) cin >> dot[i];
    sort(dot,dot+n);
    while (m--) {
        cin >> x >> y;
        cout << upper_bound(dot,dot+n,y) - lower_bound(dot,dot+n,x) << '\n';
    }
}