Search

BOJ 3020 개똥벌레

태그
이분 탐색
누적 합
생성일
2024/12/11 12:11

문제 설명

•
NN개의 장애물이 주어질 때, 파괴해야 하는 장애물의 최소값과 그러한 경우의 수를 구하는 문제

예제 입력/출력

•
입력1
6 7 1 5 3 3 5 1
Plain Text
복사
•
출력1
2 3
Plain Text
복사
•
입력2
14 5 1 3 4 2 2 4 3 4 3 3 3 2 3 3
Plain Text
복사
•
출력2
7 2
Plain Text
복사

제약 조건

•
2≤N≤200,0002 ≤ N ≤ 200,000 (NN은 짝수)
◦
1≤1 ≤ 장애물의 높이 <H< H
•
2≤H≤500,0002 ≤ H ≤ 500,000

문제 풀이

풀이1 브루트 포스 - O(H⋅N)O(H \cdot N)
풀이2 그리디
풀이3 DP - O(N+H)O(N + H)
•
풀이4 DP 사용 X - O(N+H)O(N + H)
•
풀이5 이분 탐색 - O(N⋅logN+H⋅logN)O(N \cdot logN + H \cdot logN)

풀이 코드

풀이3 DP - O(N+H)O(N + H)
풀이4 DP 사용 X - O(N+H)O(N + H)
풀이5 이분 탐색 - O(N⋅logN+H⋅logN)O(N \cdot logN + H \cdot logN)