[백준 13397번] 구간 나누기 2 (C++)

문제링크 : https://www.acmicpc.net/problem/13397

13397번: 구간 나누기 2

 

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

int n, m;

int cal(int mid, int arr[])  //해당 mid 값 갯수 계산
{
	int cnt = 1, minV = arr[0], maxV = arr[0];
	for (int i = 1; i < n; i++)
	{
		if (minV > arr[i]) minV = arr[i];
		if (maxV < arr[i]) maxV = arr[i];

		if ((maxV - minV) > mid)
		{
			cnt++;
			minV = arr[i];  //해당 값을 기준으로 다시 시작
			maxV = arr[i];  //위와 동일
		}
	}
	return cnt;
}

int binary_search(int l, int h, int arr[])
{
	int result = 0;
	while (l <= h)
	{
		int mid = (l + h) / 2;
		if (cal(mid, arr) <= m)
		{
			result = mid;
			h = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	return result;
}

int main()
{
	fastio;
	int arr[5000];
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	cout <<binary_search(0, *max_element(arr, arr+n), arr);
	return 0;
}

 

처음에 정렬부터 하고 시작했다가 틀린 답이 나왔다.

배열 값을 순서대로 확인해야 하기 때문에 정렬하지 않고, 이분탐색때 0과 배열 내 가장큰 값을 넣어준다.