[Algorithm] C++ 백준 17439번 : 꽃집

아이디어 요약

각 구간(꽃다발)의 비용은 (구간 길이) × (구간 내 가격 합)이다. 오름차순으로 주어지므로 원소 순서를 유지한 연속 구간 분할 문제다.
누적합 S[i]를 두면, j < i에서 cost(j+1..i) = (i-j)·(S[i]-S[j]) 이다. 나이브 점화식은 다음과 같다.
- dp[i] = min_{0 ≤ j < i} dp[j] + (i-j)·(S[i]-S[j]) (정확히 K개 제약이 있으면 레이어를 하나 더 둬 O(N^2 K))
N, K ≤ 5e4이므로 위 점화는 불가. Alien’s trick으로 “구간을 새로 시작할 때마다 +C 페널티”를 부여해 K 제약을 제거하고, C를 이분탐색해 사용 구간 수를 K에 맞춘다.
고정된 C에 대해 위 식은 “교점이 하나인” 형태로 정리되며, 답 후보 인덱스를 단조로 관리하는 Monotone Queue 최적화로 O(N log N)에 계산 가능하다(교점 위치를 이분탐색).
최종 정답은 min(run(C*) - K·C*, run(C*-1) - K·(C*-1))로 복원한다.

C++ 풀이

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
// 더 많은 정보는 42jerrykim.github.io에서 확인할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, K;
    if (!(cin >> N >> K)) return 0;
    K = min(K, N);
    vector<int64> v(N + 1), S(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> v[i];
        S[i] = S[i - 1] + v[i];
    }

    auto run = [&](int64 C) -> pair<int64, int> {
        // dp[i]: penalized cost up to i; cnt[i]: #segments used
        vector<int64> dp(N + 1, 0);
        vector<int> cnt(N + 1, 0);

        auto val = [&](int j, int i) -> int64 {
            return dp[j] + (int64)(i - j) * (S[i] - S[j]) + C; // start new segment at j+1
        };
        auto better = [&](int a, int b, int i) -> bool {
            return val(a, i) <= val(b, i);
        };
        auto cross = [&](int a, int b) -> int {
            // minimal i where b becomes better or equal than a
            int lo = max(a, b) + 1, hi = N, ans = N + 1;
            while (lo <= hi) {
                int mid = (lo + hi) >> 1;
                if (better(b, a, mid)) { ans = mid; hi = mid - 1; }
                else lo = mid + 1;
            }
            return ans;
        };

        struct Cand { int idx, start; };
        deque<Cand> dq;
        dq.push_back({0, 1}); // j=0 candidate becomes valid from i=1

        for (int i = 1; i <= N; ++i) {
            while ((int)dq.size() >= 2 && dq[1].start <= i) dq.pop_front();
            int j = dq.front().idx;
            dp[i] = val(j, i);
            cnt[i] = cnt[j] + 1;

            int start = 1;
            while (!dq.empty()) {
                int last = dq.back().idx;
                int t = cross(last, i);
                if (t <= dq.back().start) dq.pop_back();
                else { start = t; break; }
            }
            if (start <= N) dq.push_back({i, start});
        }
        return {dp[N], cnt[N]};
    };

    // Binary search penalty C (Alien's trick)
    int64 sumV = S[N];
    int64 lo = 0, hi = sumV * (int64)N; // safe upper bound
    int64 Cstar = hi;
    while (lo <= hi) {
        int64 mid = (lo + hi) >> 1;
        auto [costMid, cntMid] = run(mid);
        if (cntMid <= K) { Cstar = mid; hi = mid - 1; }
        else lo = mid + 1;
    }

    auto [cost1, cnt1] = run(Cstar);
    int64 ans1 = cost1 - Cstar * (int64)K;

    int64 Cprev = (Cstar == 0 ? 0 : Cstar - 1);
    auto [cost0, cnt0] = run(Cprev);
    int64 ans0 = cost0 - Cprev * (int64)K;

    cout << min(ans0, ans1) << "\n";
    return 0;
}