백준 13397 c++ "구간 나누기 2" -PlusUltraCode-

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

[필자 사고]

이분탐색 문제이지만  어떠한 값을 탐색할 지가 중요하다. 

매개변수 탐색을 생각해보자. 

문제에서 요구하는 값은 최소의 차이를 원한다. 그러면 그거를 탐색하는 형태로 mid값을 정의하자.

해당 값보다 큰차이를 보일 때마자 cnt 개수를 증가시키고 minVal 과 maxVal 의 값을 arr[i]로 새로 갱신해주는 형태

그리고 마지막에 cnt<=mid 형태를 통해 참인지 거짓인지 반환..

 

매개변수 탐색의 핵심은 역시 어떤 값을 left right으로 설정할지 인거 같다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

함수명: main()

역할:
입력된 배열을 M개 이하의 구간으로 나눌 때, 각 구간의 점수(최대값 - 최소값)의 최댓값을 최소화하는 값을 구하는 메인 제어 함수이다.

동작 순서:

1. 입력 처리:
   • 배열의 크기 N과 최대 구간 수 M을 입력받는다.
   • 이어서 배열의 원소들을 벡터 arr에 차례로 저장한다.
2. 탐색 범위 설정:
   • 가능한 점수의 최소값(left)을 0으로,
   • 가능한 점수의 최대값(right)을 정수의 최댓값(INT_MAX)으로 설정한다.
   • 답(answer)은 일단 right로 초기화한다.
3. 이분 탐색 실행:
   • 반복문(while (left <= right))을 통해 탐색 범위를 계속 줄여나간다.
   • 중간값 mid = (left + right) / 2를 “현재 가정한 최대 구간 점수”로 설정한다.
   • isPossible(mid) 함수를 호출하여,
     주어진 점수(mid)로 M개 이하의 구간으로 나눌 수 있는지 판단한다.
   • 가능한 경우(true):
     현재 점수(mid)로 나누기가 가능하므로
     answer를 mid로 갱신하고, 더 작은 점수가 가능한지 확인하기 위해 right = mid - 1로 범위를 줄인다.
   • 불가능한 경우(false):
     현재 점수(mid)가 너무 작아서 구간을 M개 이하로 만들 수 없으므로,
     left = mid + 1로 탐색 범위를 키운다.
4. 결과 출력:
   반복이 종료되면, 가능한 최솟값이 answer에 저장되어 있으므로 이를 출력한다.

---

함수명: isPossible(int mid)

역할:
주어진 최대 점수(mid) 이하로 배열을 M개 이하의 구간으로 나눌 수 있는지를 판별하는 함수이다.

세부 동작:

1. 초기화:
   • 구간의 개수를 cnt = 1로 설정한다.
   • 첫 번째 원소를 기준으로 현재 구간의 최소값(minVal)과 최대값(maxVal)을 초기화한다.
2. 배열 순회:
   • 배열을 왼쪽부터 오른쪽으로 순서대로 탐색한다.
   • 각 원소를 현재 구간에 추가하면서
     minVal = min(minVal, arr[i]),
     maxVal = max(maxVal, arr[i])로 갱신한다.
3. 새 구간 분할 조건:
   • 현재 구간의 점수(maxVal - minVal)가 mid를 초과하면,
     하나의 구간이 더 필요하다고 판단하여 cnt++를 수행한다.
   • 새로운 구간을 시작하기 위해
     minVal과 maxVal을 현재 원소(arr[i])로 재설정한다.
4. 판단:
   • 전체 배열을 끝까지 순회한 후,
     만들어진 구간의 개수 cnt가 M 이하라면 주어진 점수로 나누기가 가능하므로 true를 반환한다.
   • M을 초과한다면 불가능하므로 false를 반환한다.

---

전체 알고리즘 개요

1. main()에서 이분 탐색을 수행하여
   가능한 최대 점수(mid)를 점점 줄여나가며 최솟값을 찾는다.
2. isPossible(mid) 함수는
   주어진 점수 제한(mid)으로 실제 배열을 순차적으로 탐색하며
   몇 개의 구간이 필요한지를 계산한다.
3. 가능한 구간 수가 M 이하이면 더 작은 점수도 시도해보고,
   초과하면 점수를 늘려 탐색한다.
4. 결국, M개 이하의 구간으로 나눌 수 있는
   가장 작은 최대 점수가 정답이 된다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int N, M;

vector<int> arr;

bool isPossible(int mid) {
	int cnt = 1;
	int minVal = arr[0];
	int maxVal = arr[0];

	for (int i = 1; i < N; i++) {
		minVal = min(minVal, arr[i]);
		maxVal = max(maxVal, arr[i]);

		if (maxVal - minVal > mid) {
			cnt++;
			minVal = arr[i];
			maxVal = arr[i];
		}
	}

	return cnt <= M;
}

int main(void) {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}

	int left = 0;
	int right = INT_MAX;
	int answer = right;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (isPossible(mid)) {
			answer = mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	cout << answer;
}