Search
Duplicate

BOJ 13397 구간 나누기 2

태그
이분 탐색
매개 변수 탐색
생성일
2024/09/09 03:55

문제 설명

•
NN개의 수에 대해 MM개 이하의 구간으로 나누었을 때, 구간의 점수의 최대값의 최소값을 구하는 문제
◦
구간의 점수 = 구간의 속한 수의 최대값과 최소값의 차이

예제 입력/출력

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

제약 조건

•
1≤N≤5,0001 ≤ N ≤ 5,000
•
1≤M≤N1 ≤ M ≤ N
•
배열의 원소에 대한 정보
◦
1≤1 ≤ 원소의 값 ≤10,000≤ 10,000

문제 풀이

접근1 브루트 포스 - O(10,000⋅N)O(10,000 \cdot N)
접근2 그리디
접근3 DP - O(N2⋅M)O(N^2 \cdot M)
접근4 파라매트릭 서치 - O(14⋅N)O(14 \cdot N)

풀이 코드

접근1 브루트 포스 - O(10,000⋅N)O(10,000 \cdot N)
접근3 DP - O(N2⋅M)O(N^2 \cdot M)
접근4 파라매트릭 서치 - O(14⋅N)O(14 \cdot N)