[1. 문제 설명]
https://www.acmicpc.net/problem/3020
[2. 풀이 접근]
이분 탐색을 이용한 풀이
=> 코드 참조
부분 합을 이용한 풀이
장애물 별 높이에 대해서 해당 높이를 갖는 장애물이 몇개인지 저장 할 수 있다.
- H 는 최대 500,000 이므로, 1,000,000 개의 메모리 확보 가능
이분 탐색을 이용한 풀이와 마찬가지로 접근 해 볼 수 있다.
- 구간 합을 이용해서 어떤 높이 r 부터 H 까지 총 몇개가 있는지 확인 할 수 있다.
[3. 코드]
'알고리즘 > Baekjoon' 카테고리의 다른 글
| 스택. [2493] (0) | 2023.02.08 |
|---|---|
| 스택. [10799] (0) | 2023.02.07 |
| 부분 합. [2143] (0) | 2023.01.31 |
| 이분 탐색. [2343] (0) | 2023.01.29 |
| 이분 탐색. [2467] (0) | 2023.01.28 |