[백준 26105] Folding Stick (ICPC 2022 Seoul Regional D; Platinum III)

 주어진 수열을 연속된 것들끼리 몇 묶음으로 묶되, 묶음에 포함된 막대기들의 길이의 합이 감소하지 않는 수열을 이루도록 하는 문제로 치환할 수 있다. (단, 마지막 묶음만 빼고...)

 예를 들어 예제의 1 3 2 3 4 2 2는 다음과 같이 묶일 수 있다: (1 3) (2 3) (4 2) (2)

 이렇게 묶이면 각각의 묶음이 4 5 6 2가 되어 마지막 묶음만 빼고 감소하지 않는 수열이 된다. (4 <= 5 <= 6) 이렇게 되었을 때 문제의 요구사항대로 접을 수 있음은 자명하다.

 

 마지막 묶음만 뺀다는 조건이 좀 걸리적거리니, 이 제약조건을 없앤 채로 문제를 푼 다음에, 그 결과로 제약조건이 있었던 원래 문제의 결과를 복원할 수 있지 않을까 하는 생각을 하게 된다. g(i)를 (0~i번째 막대기를 사용하여 묶음을 만들었을 때, 마지막 묶음을 포함하여 감소하지 않는 수열이 될 때, 그 수열에서 가장 큰 항의 최솟값)이라 정의하자. 예를 들어 막대기 = 1 3 2 3 4 2 2일 때 g(6)=8이다. (1 3) (2 3) (4 2 2)로 묶여야 가장 큰 항의 값이 8이고 이 값이 최소이므로. 이제 다음 사실이 성립한다.

 (구하고자 하는 값) = \( \min_{i < n} (\max(g(i), \operatorname{sum}(v[i+1]..v[n-1]) \)

 따라서 모든 i에 대해 g(i)의 값을 dp로 빠르게 구해 줄 생각을 해 보자. 다음이 성립한다.

 $$ g(i) = \min_{j < i} \operatorname{sum}(v[j+1]..v[i]) \mbox{ if } \operatorname{sum}(v[j+1]..v[i]) \geq g(j) $$

 v의 누적 합 배열을 S라 하면 (단, S[0] = v[0]) 다음과 같이 바뀐다.

 $$ g(i) = \min_{j < i} S[i]-S[j] \mbox{ if } S[i]-S[j] \geq g(j) $$

 이 조건을 만족하는 j를 각 i마다 일일이 찾아 주면 \(O(N^2)\)이 걸린다. 더 빠른 방법이 필요하다. 일단 \(S[i]-S[j]\)의 값은 j가 증가할수록 감소한다. 따라서 주어진 조건식을 만족시키는 최대의 j를 찾는 것으로 족하다. 한편 조건식은 이항하면

 $$ g(j) + S[j] \leq g(i) $$

 가 된다. 좌변에 해당하는 식은 이미 우리가 잘 알고 있는 값이며, 어디다 들고 있는 것이 가능하다. 왜냐하면 \(S[j]\)들의 값은 이미 알고 있고, \(g(j)\)의 값은 \(j < i\) 조건에서 \(g(i)\)를 계산하기 전에 이미 \(g(j)\)를 계산했을 테니 dp 배열에 들어 있을 것이다. 

 원래 이런 문제를 빠르게 푸는 방법으로 이분 탐색을 떠올릴 수 있다. 그러나 안타깝게도 \(g(j) + S[j]\)가 항상 증가수열이라는 보장은 없다. 예를 들어 막대기 = 10 9 1 7 6일 때

 S[i] = 10 19 20 27 33

 g(i) = 10 19 10 17 13

 S[i] + g(i) = 20 38 30 44 46

 으로 증가수열이 아니다... 관찰이 더 필요하다. 우리가 원하는 것은 \(g(j) + S[j] \leq x\)(x는 임의로 주어지는 값)을 만족시키는 최대의 j를 찾는 일이다. 그렇다면 위의 사례에서, 그 최대의 j로 1이 나올 일이 있을까? 만약 \(38 = g(1) + S[1] \leq x\)라면, \(30 < 38\)이므로 \(g(2) + S[2] \leq x\)이다. 따라서 j = 1이 주어진 부등식을 만족하면 j = 2도 주어진 부등식을 만족한다. 그래서 \(g(1) + S[1] \geq g(2) + S[2]\)임을 발견한 순간 j = 1은 고려 대상에서 제외해도 무방하다.

 이제 풀이를 설계할 수 있다. \(S[i] + g(i)\)의 값을 관리하는 monotone stack을 만든다. stack 내부의 값은 증가수열을 이루도록 관리해줄 수 있다. 이제 주어진 부등식을 만족하는 최대의 j를 이분 탐색으로 찾는다. monotone stack이기에 이분 탐색이 가능하다.

 

 시간복잡도는 \(O(n \log n)\)이다.

 

#include <bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    
    std::vector<i64> vec(n, 0), pfs(n, 0), dp(n, 0);
    std::vector<std::pair<i64, int>> stack;
    for (auto& x : vec) std::cin >> x;
    
    pfs[0] = vec[0];
    for (int i = 1; i < n; ++i) {
        pfs[i] = pfs[i - 1] + vec[i];
    }
    
    dp[0] = vec[0];
    stack.emplace_back(dp[0] + pfs[0], 0);
    
    for (int i = 1; i < n; ++i) {
        auto it = std::upper_bound(stack.begin(), stack.end(), std::pair{pfs[i], n});
        int k = [&] {
            if (it == stack.begin()) return -1;
            else return (it - 1)->second;
        }();
        i64 dp_val = [&] {
            if (k >= 0) return pfs[i] - pfs[k];
            else return pfs[i];
        }();
        dp[i] = dp_val;
        while (!stack.empty() && stack.back().first >= dp_val + pfs[i]) stack.pop_back();
        stack.emplace_back(dp_val + pfs[i], i);
    }
    
    i64 ret = pfs.back();
    for (int i = 0; i < n; ++i) {
        ret = std::min(ret, std::max(dp[i], pfs[n - 1] - pfs[i]));
    }
    
    std::cout << ret << "\n";
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    solve();
    return 0;
}

 

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

26105번: Folding Stick