[백준 13397] 구간 나누기 2 (C#, C++) - soo:bak

문제 링크

13397번 - 구간 나누기 2

설명

배열을 최대 m개의 구간으로 나눌 때, 각 구간의 점수를 최댓값과 최솟값의 차이로 정의합니다. 모든 구간 점수 중 최댓값을 최소화하는 문제입니다.

접근법

구간 점수의 최댓값이 특정 값 이하가 되도록 나눌 수 있는지 판별하는 문제로 바꿔 생각합니다. 이 값을 이분 탐색으로 찾습니다.

어떤 상한값이 주어지면 배열을 왼쪽부터 훑으면서 현재 구간의 최솟값과 최댓값을 유지합니다. 둘의 차이가 상한을 넘으면 바로 이전까지를 하나의 구간으로 끊고, 현재 원소부터 새 구간을 시작합니다. 끝까지 훑었을 때 구간 수가 m개 이하이면 그 상한값은 달성 가능합니다.

이분 탐색의 범위는 0부터 배열의 최댓값까지입니다. 달성 가능한 상한값 중 가장 작은 것을 출력합니다.

---

Code

C#

using System;
using System.Linq;

class Program {
  static int n, m;
  static int[] arr = Array.Empty<int>();

  static bool Can(int limit) {
    var groups = 1;
    var mn = arr[0];
    var mx = arr[0];
    for (var i = 1; i < n; i++) {
      mn = Math.Min(mn, arr[i]);
      mx = Math.Max(mx, arr[i]);
      if (mx - mn > limit) {
        groups++;
        mn = mx = arr[i];
      }
    }
    return groups <= m;
  }

  static void Main() {
    var first = Console.ReadLine()!.Split();
    n = int.Parse(first[0]);
    m = int.Parse(first[1]);
    arr = Console.ReadLine()!.Split().Select(int.Parse).ToArray();

    var lo = 0;
    var hi = arr.Max();
    var ans = hi;
    while (lo <= hi) {
      var mid = (lo + hi) / 2;
      if (Can(mid)) {
        ans = mid;
        hi = mid - 1;
      } else lo = mid + 1;
    }
    Console.WriteLine(ans);
  }
}

C++

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

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  vi a(n);
  for (int i = 0; i < n; i++) cin >> a[i];

  auto can = [&](int lim) {
    int groups = 1;
    int mn = a[0], mx = a[0];
    for (int i = 1; i < n; i++) {
      mn = min(mn, a[i]);
      mx = max(mx, a[i]);
      if (mx - mn > lim) {
        groups++;
        mn = mx = a[i];
      }
    }
    return groups <= m;
  };

  int lo = 0, hi = *max_element(a.begin(), a.end()), ans = hi;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (can(mid)) {
      ans = mid;
      hi = mid - 1;
    } else lo = mid + 1;
  }
  cout << ans << "\n";

  return 0;
}