BOJ 5821 쌀 창고

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

5821번: 쌀 창고

 

쌀 창고의 위치가 주어지고 쓸 수 있는 비용이 주어질 때 해당 비용 내에서 최대한 많은 쌀을 옮기는 문제입니다.

 

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

2375번: 농구 골대 세우기

 

위 문제의 아이디어를 이용하면 어떤 점들이 주어졌을 때 해당 점들과의 거리의 합이 최소가 되는 점은 중앙값이라는 것을 알 수 있습니다. 증명은 그래프의 개형을 그려서 할 수 있습니다. 한 점과 어떤 점의 거리는 두 점의 위치가 같을 때 0이고, 왼쪽으로 멀어지거나 오른쪽으로 멀어질수록 값이 커지는 볼록 함수의 모양을 하고 있습니다. 볼록 함수와 볼록 함수를 더한 함수의 개형 역시 볼록이기 때문에, 거리의 합의 함수 역시 볼록한 모양을 띄고 있습니다. 따라서 여기서 가장 값이 작은 부분, 즉 아래로 볼록한 부분을 찾으면 거리의 합이 최소화되는 점이 됩니다. 해당 점은 왼쪽과 오른쪽의 점의 갯수가 같은 지점, 즉 중앙값인데 이는 기울기를 잘 생각해보면 알 수 있습니다. 어떤 점에서의 기울기는 해당 점보다 왼쪽에 있는 점의 갯수와 오른쪽에 있는 점의 갯수에 따라 결정됩니다. 한 칸 이동했을 때 비용이 $abs(l - r)$만큼 증가하기 때문입니다. 따라서 아래로 볼록한 지점, 즉 기울기가 0이 되는 지점은 중앙값입니다.

 

위 아이디어를 이용하면 쌀 창고의 구간이 주어졌을 때, 해당 쌀 창고들을 커버하는데 필요한 최소 비용을 알 수 있습니다. 이는 나이브하게 구현하면 $\mathcal{O}(n)$에, 누적합을 써서 최적화를 하면 $\mathcal{O}(1)$에 구할 수 있습니다. 식을 정리하면 (중앙값의 좌표 * 왼쪽에 있는 점의 갯수) - (왼쪽에 있는 점의 좌표의 누적합)에 (오른쪽에 있는 점의 좌표의 누적합) - (중앙값의 좌표 * 오른쪽에 있는 점의 갯수)를 더한 값이 최소 비용이 되기 때문입니다.

 

마지막으로 쌀 창고를 커버하는데 필요한 최소 비용은 단조성을 띄므로 투포인터를 이용해 쌀 창고의 구간의 왼쪽과 오른쪽을 관리해줍니다. 해당 구간이 현재 예산으로 커버가 가능하면 오른쪽을 1 증가시켜 구간을 증가시켜주고, 아니라면 왼쪽을 1 증가시켜 구간을 감소시켜줍니다. 해당 과정에서 커버가 가능한 가장 많은 쌀 창고의 수가 답이 됩니다.

 

아래는 코드입니다.

 

#include <bits/stdc++.h>
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define ends ' '
#define int long long

using namespace std;

int T, n, l, b, arr[100010];
vector<int> vec;

int check(int l, int r, int m, int cnt) {
  int sum = 0;
  sum += (cnt - (r - m + 1)) * vec[m] - (arr[m - 1] - arr[l - 1]);
  sum += (arr[r] - arr[m]) - (cnt - (m - l + 1)) * vec[m];
  if (sum <= b) return 1;
  return 0;
}

int32_t main(void) {
  FastIO;
  T = 1;

  while (T--) {
    cin >> n >> l >> b;

    vec.resize(n + 1);
    for (int i = 1; i <= n; i++) cin >> vec[i];
    for (int i = 1; i <= n; i++) arr[i] = arr[i - 1] + vec[i];

    int l = 1;
    int r = 1;
    int ans = 0;

    while (r <= n) {
      int cnt = r - l + 1;
      int m = cnt / 2;
      if (cnt % 2 == 0) m--;
      m += l;

      if (check(l, r, m, cnt)) {
        ans = max(ans, cnt);
        r++;
      }
      else l++;
    }

    cout << ans << endl;
  }

  return 0;
}