Solution

Memo

  • 파라메트릭서치
  • 파라메트릭 서치로 ‘분류’되는 문제인걸 알아서 겨우 푼 것 같다.
  • 이런 방법을 생각할 수 있을까 싶으면서도
  • 뭔가 조금 더 최적화된 브루트포스 풀이를 생각하면 좋은 것 같다
  • 브루트포스 > dp > 파라메트릭 이순서로 가능? 하면서 생각해보면 좋을것같다.
  • can_split 함수는 그리디로 구현했다.
    • 새로운 원소마다 최대값 최소값을 갱신해서 만약 지금 상태의 배열이 파라메트릭으로 선정된 최대값보다 작다면 원소를 더 추가하고
    • 크다면 새로운 배열을 생성한다.
    • 결국 배열을 전부 만들었을때, 조건을 달성했는지 판별한다.
// Baekjoon - 13397
// https://www.acmicpc.net/problem/13397

use std::cmp::{max, min};
use std::io::{self, Read, Write};

fn main() {
    let mut stdin = io::stdin().lock();
    let mut stdout = io::stdout().lock();
    let mut input = String::new();
    stdin.read_to_string(&mut input).unwrap();
    let mut lines = input.lines();

    let meta_line: Vec<usize> = lines.next().unwrap()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    let _n = meta_line[0];
    let m = meta_line[1];

    let nums: Vec<usize> = lines.next().unwrap()
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    if nums.iter().min() == nums.iter().max() {
        writeln!(stdout, "0").unwrap();
        return;
    }

    let mut left: usize = 0;
    let mut right = *nums.iter().max().unwrap();
    let mut output = right;

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

        if can_split(&nums, m, mid) {
            output = mid;
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    write!(stdout, "{}", output).unwrap();
}

fn can_split(nums: &[usize], m: usize, max_score: usize) -> bool {
    let mut count: usize = 1;

    let mut count_min = nums[0];
    let mut count_max = nums[0];

    for i in 1..nums.len() {
        let tmp_min = min(count_min, nums[i]);
        let tmp_max = max(count_max, nums[i]);

        if tmp_max - tmp_min > max_score {
            count += 1;
            count_min = nums[i];
            count_max = nums[i];
        } else {
            count_min = tmp_min;
            count_max = tmp_max;
        }
    }

    count <= m
}