[G4] 백준 13397번 구간 나누기 2 C++ 이분 탐색, 매개 변수 탐색

리뷰

 

https://www.acmicpc.net/problem/13397

파라매트릭 서치의 기본이 되는 문제

 

 

전역 변수

• n : 배열의 크기를 저장할 변수
• m : 구간의 개수를 저장할 변수
• ans : 정답을 저장할 변수
• lst : 배열 정보를 저장할 정수형 배열

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받고, lst배열에 n개의 배열 요소를 입력받아 준다.
2. l을 0, r을 10000으로 초기화 해주고 l이 r보다 이하일 경우 while루프를 반복해 준다.
3. 정수형 변수 mid를 l + r을 2로 나눈 값으로 저장해 준다.
4. 구간의 개수 cnt를 1로, 최대 및 최소값 MAX, MIN을 lst배열의 첫 인자로, diff를 MAX-MIN값으로 초기화 한다.
5. 배열의 두번째 요소부터 마지막 요소까지 for문을 통해 순회해 준다.
6. 현재 요소가 MAX보다 크면 MAX를 현재 요소로, MIN보다 작으면 MIN을 현재 요소로 변경해 준다.
7. diff값을 MAX-MIN으로 다시 저장해 준다.
8. 만약 diff가 mid보다 크다면 cnt를 증가시키고, MAX, MIN을 현재 요소로, diff를 0으로 초기화 한다.
9. 탐색을 마친 후 cnt가 m보다 크다면 l을 mid + 1로 변경해 준다.
10. cnt가 m보다 작거나 같다면 ans를 mid와 비교하여 더 작은 값으로 갱신하고 r을 mid - 1로 변경해 준다.
11. 모든 탐색을 마친 후 ans에 저장된 값을 출력해 준다.

 

트러블 슈팅

없음

 

 

참고 사항

• 초기 및 cnt증가 시 diff를 0으로 초기화 해도 된다. 가독성을 위해 MAX-MIN으로 명시해 주었다.

 

정답 코드

#include<iostream>
using namespace std;

int n, m, ans = 10000;
int lst[10000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; ++i) cin >> lst[i];

	int l = 0, r = 10000;
	while (l <= r) {
		int mid = (l + r) / 2;

		int cnt = 1;
		int MAX = lst[0];
		int MIN = lst[0];
		int diff = MAX - MIN;
		for (int i = 1; i < n; ++i) {
			if (MAX < lst[i]) MAX = lst[i];
			else if (MIN > lst[i]) MIN = lst[i];

			diff = MAX - MIN;
			if (diff > mid) {
				cnt++;
				MAX = lst[i];
				MIN = lst[i];
				diff = MAX - MIN;
			}
		}

		if (cnt > m) l = mid + 1;
		else {
			ans = min(ans, mid);
			r = mid - 1;
		}
	}
	cout << ans;
}