문제1325--[창의적 알고리즘(중급)] lower bound

1325: [창의적 알고리즘(중급)] lower bound

[만든사람 : 창의적알고리즘(중급), 전현석(채점데이터, 2021)]
시간제한 : 1.000 sec  메모리제한 : 128 MiB

문제 설명

n개로 이루어진 정수 집합에서 원하는 수 k이상인 수가 처음으로 등장하는 위치를 찾으시오.

단, 입력되는 집합은 오름차순으로 정렬되어 있으며, 같은 수가 여러 개 존재할 수 있다.

입력 설명

첫 번째 줄에 한 정수 n이 입력된다.
두 번째 줄에 n개의 정수가 공백으로 구분되어 입력된다.
세 번째 줄에는 찾고자하는 값 k가 입력된다.
(2<=n<=1,000,000)
(0<=k<=100,000,000)

출력 설명

찾고자하는 원소의 위치를 출력한다.
만약 모든 원소가 k보다 작으면 n+1을 출력한다.

주의!
lower bound 는 영어 의미 그대로 이해하는 것이 좋다.
어떤 집합을 정렬된 상태로 상태로 유지하면서
새로운 값을 삽입해 넣을 수 있는 가장 아래쪽(lower) 경계(bound) 위치라고 생각하면 정확하다.

입력 예시 Copy

5
1 3 5 7 7
7

출력 예시 Copy

4

도움

- 문제해결을 위한 창의적 알고리즘(중급)