백준 13397 : 구간 나누기 2

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

13397번: 구간 나누기 2

[ 문제풀이 ]

최적해를 구하는 문제이기 때문에 결정 문제로 변경하여 파라메트릭 서치를 활용하면 해결할 수 있는 문제이다.

key 값을 기준으로 구간을 나눴을 때 M보다 작다면 정답이 가능하기 때문에 더 작은 key값을 탐색해주고, M보다 크다면 정답이 불가능하기 때문에 더 큰 key값으로 탐색해준다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	
	static int N, M;
	static int[] data;
	
	public static void main(String[] args) {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			data = new int[N + 1];
			st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= N; ++i) {
				data[i] = Integer.parseInt(st.nextToken());
			}
			
			int l = 0, r = 10001;
			while (l <= r) {
				int m = (l + r) >> 1;
				if (isValid(m)) r = m - 1;
				else l = m + 1;
			}
			bw.write(l + "\n");
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	
	public static boolean isValid(int key) {
		int count = 1, min = 10001, max = -1;
		for (int i = 1; i <= N; ++i) {
			min = Math.min(min, data[i]);
			max = Math.max(max, data[i]);
			if (max - min > key) {
				count++;
				min = 10001;
				max = -1;
				i--;
			}
		}
		return count <= M;
	}
}