[백준][C++] 13397번: 구간 나누기 2 <178>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

13397번: 구간 나누기 2

생각의 흐름

맨 처음 든 생각은 구간을 어떻게 나누지? 였다.

또한 brute force 계열의 문제라고 생각했다. 하나하나 구간을 나눠서 찾아야 한다 생각했다.

하지만 N이 5천이나 되기 때문에 시간안에 불가능할것 같았다.

 

최대 5천명을, 3구간으로만 나누라 해도 너무 많은 case가 있다.

더구나 이 문제에서는 M이하 의 구간으로 나눌수 있기 때문에 case가 너무 많다,

 

따라서 이분탐색을 사용하기로 하였다.

구해야 하는 대상인 최대값중 최솟값을 mid 값으로 잡으면서 조율해 나가면 된다.

 

2분 탐색 매 반복마다 그럼 어떤과정을 검증해야 할까?

구한 mid값 보다 큰 구간이 M개 이하 가 되도록 수행해야 한다.

 

위 말이 좀 이해가 안갈수 있다. 다시 풀어서 설명해 보겠다.

mid 라는 값은 어떠한 구간(a, b, c ~ f) 에서 (최대값 - 최소값)중 최대값중에 최소값 해당되는 값이다.

 

주어진 배열의 앞부터 차례로 탐색할때, max값과 min값을 갱신하면서 차이를 구한다.

이 차이가 mid 값보다 크면 구간이 하나 만들어 지게 된다. 왜냐하면 우리의 mid값은 구간의 차이값들 중에서는 최소에 해당되기 때문이다. mid값보다 큰 차이값을 갖는 구간이 구간의 조건은 만족한다 할 수 있다.

 

따라서 cnt 변수에 +1을 해준다.

 

이렇게 만들어진 구간의 수가 최대 구간의  수인 M보다 작거나 같아야 한다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 5001

int N, M;
int arr[MAX];
int res = INT_MAX;

bool isPossible(int mid){
	int cnt = 1;
	int minV = arr[0], maxV = arr[0];
	
	for(int i = 1; i < N; i++){
		if(arr[i] < minV) minV = arr[i];
		if(arr[i] > maxV) maxV = arr[i];
		
		if((maxV - minV) > mid){
			cnt++;
			minV = arr[i];
			maxV = arr[i];
		}
	}
	return cnt <= M;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M;
	for(int i = 0; i < N; i++){
		cin >> arr[i];
	}
	
	int right = *max_element(arr, arr+N);
	int left = 0;
	
	while(left <= right){
		int mid = (left + right) / 2;
		
		if(isPossible(mid)){
			if(res > mid) res = mid;
			right = mid - 1;
		}else{
			left = mid + 1;
		}
	}
	
	cout << res;
	
	return 0;
}