문제
구간은 [s, e] 로 나타내고, 이 의미는 s, (s+1), (s+2), …, (e-1), e 와 같이 숫자를 나열한 것을 의미한다. 예를 들어, [1, 4]는 1, 2, 3, 4로 숫자를 나열한 것을 의미한다. n개의 구간이 있고, 이 구간들의 숫자를 모두다 새로운 배열 S에 넣어 정렬을 한다. 이 때 S[i] 의 값이 무엇인지 출력하는 프로그램을 작성하시오. 예를 들어, 3개의 구간 [1, 3], [2, 10], [1, 8] 이 있고, S[5]를 알고싶다고 하자. 그러면 S = [1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 10] 이 되고, 따라서 S[5]는 3이 된다. 배열의 인덱스는 0부터 시작한다는 것에 주의하자.
입력
첫 번째 줄에 구간의 개수 n이 주어진다 ( 1 ≤ n ≤ 10,000 ) 두 번째 줄부터 각 구간을 나타내는 숫자 s, e가 주어진다. ( 1 ≤ s ≤ e ≤ 1,000,000,000 ) 그 후, 마지막 줄에는 값을 알고 싶은 숫자의 위치 i가 주어진다. ( 1 ≤ i ≤ 10,000,000,000,000 ) i번째 위치에는 항상 숫자가 존재한다고 가정한다.
출력
S[i]를 출력한다.
예제 입력
2
1 4
3 5
3
예제 출력
3
예제 입력
3
1 3
2 10
1 8
5
예제 출력
3
이 문제는 NN단표와 풀이 방식이 비슷한 문제이다. 두번째 예제로 풀이예시를 들어보면 주어진 범위가 1~3 / 2~10 / 1~8 이다.
여기에서 최솟값 1과 최댓값 10을 정하고, 이진탐색을 수행하면 되는 문제인데, 먼저 1과 10의 중간값 5보다 같거나 작은 개수를 구하고, 만약에 그 개수가 최종적으로 구하는 숫자의 위치보다 작거나, 같거나, 클때로 나누어 이진탐색을 해서 푸는 문제이다. 여기에서 주의할점은 문제에 나와있듯이 배열의 인덱스는 0부터 시작한다는 점과 만약에 개수가 (코드에서는 sum) 구하는 위치와 같게 된다면 바로 그 다음에 있는 수가 정답이 되는 것이다.
처음에 mid값보다 작을때로 생각하여 풀었는데 계속 50~60점이 나와서 같거나 작을 때로 바꿔서 풀고, mid값보다 작거나 같은 개수를 구할때 범위를 잘못정해서 답이 안나와서 엄청 오래 고민한 문제였다.