BOJ 13397 구간 나누기 2

문제

N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다.

1. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다.
2. 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다.

구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다.
예를 들어, 배열이 [1, 5, 4, 6, 2, 1, 3, 7] 이고, M = 3인 경우가 있다.
이때, [1, 5], [4, 6, 2], [1, 3, 7]로 구간을 나누면 각 구간의 점수는 4, 4, 6점이 된다. 이때, 최댓값은 6점이다.
만약, [1, 5, 4], [6, 2, 1], [3, 7]로 구간을 나누었다면, 각 구간의 점수는 4, 5, 4점이 되고, 이때 최댓값은 5점이 된다.
두 경우 중에서 최댓값이 최소인 것은 5점인 것이고, 5점보다 최댓값을 작게 만드는 방법은 없다.
배열과 M이 주어졌을 때, 구간의 점수의 최댓값의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 N과 M이 주어진다. (1 ≤ N ≤ 5,000, 1 ≤ M ≤ N)
둘째 줄에 배열에 들어있는 수가 순서대로 주어진다. 배열에 들어있는 수는 1보다 크거나 같고, 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 구간의 점수의 최댓값의 최솟값을 출력한다.

---

풀이

시간 안에 풀지 못하여 해설을 봤습니다.
해설에 의하면, 최적화 문제를 결정 문제로 바꾸어 푸는 매개변수 탐색이라고 합니다.
아직 최적화 문제를 결정 문제로 바꾸어 푸는 법에 익숙하지 않은 것 같습니다.

• 최적화 문제: 0~N의 배열을 모두 방문해서 각 구간 점수를 구하여 최솟값을 반환한다.
• 결정 문제: 0~N의 배열을 모두 방문해서 구간 점수가 mid보다 큰 값을 포함한 구간 집합의 수가 m보다 큰지 여부를 반환한다.

최댓값과 최솟값의 차이가 mid 이하가 되도록 수열을 m개 이하의 구간으로 나눌 수 있는가? 라는 결과를 놓았다.

코드

public class B13397 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		// 구간의 점수 = 구간에 속산 수의 최댓값과 최솟값의 차
		int left = 0; // 구간의 점수가 가장 작은 경우
		int right = 0; // 구간의 점수가 가장 큰 경우
		
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			right = Math.max(right, arr[i]);
		}
		
		while(left < right) {
			int mid = (left + right) / 2; // 구간의 점수가 (left + right) / 2인 구간의 점수 구하기
			
			int cnt = divide(arr, mid); // 구한 구간의 점수로 나눌 시 몇 개의 구간이 만들어지는지 구하기
			
			if(cnt <= m) // 나눠진 구간의 개수가 m 개보다 적거나 같으면 더 나눠도 됨.
				right = mid;  // 즉, right 를 mid 값으로 지정하여 구간의 점수가 더 작아지게 함. 구간의 점수가 더 작아지면 구간이 더 잘게 나누어질 수 있음.
			else  // 반대로 나눠진 구간의 개수가 m 개보다 많으면 덜 나누어야 함.
				left = mid + 1; // 즉, left 를 mid + 1로 올려, 구간의 점수가 더 커지게 함.
		}
		
		System.out.println(right);
		
	}
	static int divide(int[] arr, int mid) { // 순차 탐색하면서 구간의 점수가 넘지 않는 요소를 묶음
		int count = 1;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		
		for(int i = 0; i < arr.length; i++) {
			min = Math.min(min, arr[i]);
			max = Math.max(max, arr[i]);
			
			if(max - min > mid) {
				count++;
				min = Integer.MAX_VALUE;
				max = Integer.MIN_VALUE;
				i--;
			}
		}
		
		return count;
	}
}

아직 최적화 문제와 결정 문제에 대한 감이 오진 않는 것 같다.

https://blog.naver.com/jinhan814/222156334908
좀 더 공부를 해야 할 것 같다.