[Algorithm] C++ 백준 1659번 : 수 (Hard)

아이디어 요약

S, T를 하나의 정렬된 시퀀스로 병합해 인덱스 i마다 타입(+1=S, -1=T)과 값 value[i]를 기록합니다.
두 가지 선택으로 DP를 구성합니다.
- 약한 연결: i를 가장 가까운 반대 타입 원소와 연결. 비용은 좌우 이웃 중 더 가까운 거리.
- 강한 연결: 마지막으로 같은 균형(prefixDiff)을 보인 위치 j 이후 구간 (j+1..i)을 일대일(비교차)로 묶기. 이때 최소 비용은 |(구간 S 합) - (구간 T 합)|로 O(1)에 계산됩니다.
점화식: dp[i] = min(dp[i-1] + nearestOppDist[i], dp[j] + |sumS(i)-sumS(j) - (sumT(i)-sumT(j))|).
j는 prefixDiff 값이 같은 마지막 인덱스로 해시/배열에 저장하며, 초기 상태로 균형 0의 인덱스를 -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
85
86
// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> S(n), T(m);
    for (int i = 0; i < n; ++i) cin >> S[i];
    for (int j = 0; j < m; ++j) cin >> T[j];

    // 병합: value, type(+1=S, -1=T)
    const int N = n + m;
    vector<long long> value(N);
    vector<int> type(N); // +1 for S, -1 for T
    {
        int i = 0, j = 0, k = 0;
        while (i < n || j < m) {
            if (j == m || (i < n && S[i] <= T[j])) { value[k] = S[i]; type[k] = +1; ++i; }
            else { value[k] = T[j]; type[k] = -1; ++j; }
            ++k;
        }
    }

    // 균형 prefixDiff, 그리고 S/T 값 누적합
    vector<int> prefixDiff(N);
    vector<long long> prefS(N), prefT(N);
    for (int i = 0; i < N; ++i) {
        prefixDiff[i] = (i ? prefixDiff[i - 1] : 0) + type[i];
        prefS[i] = (i ? prefS[i - 1] : 0LL) + (type[i] == +1 ? value[i] : 0LL);
        prefT[i] = (i ? prefT[i - 1] : 0LL) + (type[i] == -1 ? value[i] : 0LL);
    }

    // 각 i의 가장 가까운 반대 타입 거리 (약한 연결 비용)
    const long long INF = (long long)4e18;
    vector<long long> nearestOppDist(N, INF);
    int lastS = -1, lastT = -1;
    for (int i = 0; i < N; ++i) {
        if (type[i] == +1) { if (lastT != -1) nearestOppDist[i] = min(nearestOppDist[i], value[i] - value[lastT]); lastS = i; }
        else { if (lastS != -1) nearestOppDist[i] = min(nearestOppDist[i], value[i] - value[lastS]); lastT = i; }
    }
    int nextS = -1, nextT = -1;
    for (int i = N - 1; i >= 0; --i) {
        if (type[i] == +1) { if (nextT != -1) nearestOppDist[i] = min(nearestOppDist[i], value[nextT] - value[i]); nextS = i; }
        else { if (nextS != -1) nearestOppDist[i] = min(nearestOppDist[i], value[nextS] - value[i]); nextT = i; }
    }

    // dp[i]: 0..i까지 조건 만족 최소 비용
    vector<long long> dp(N);
    // 균형값 -> 마지막 인덱스. 균형 0의 시작 위치를 -1로 설정
    int offset = N + 5;
    vector<int> lastIndex(2 * offset + 1, INT_MIN);
    auto getLast = [&](int bal) -> int {
        int idx = bal + offset;
        if (idx < 0 || idx >= (int)lastIndex.size()) return INT_MIN;
        return lastIndex[idx];
    };
    auto setLast = [&](int bal, int pos) {
        int idx = bal + offset;
        if (0 <= idx && idx < (int)lastIndex.size()) lastIndex[idx] = pos;
    };
    setLast(0, -1);

    for (int i = 0; i < N; ++i) {
        long long best = (i > 0 ? dp[i - 1] : 0LL) + nearestOppDist[i];

        int bal = prefixDiff[i];
        int j = getLast(bal); // j < i 이고 prefixDiff[j] == prefixDiff[i]
        if (j != INT_MIN) {
            long long sumS = prefS[i] - (j >= 0 ? prefS[j] : 0LL);
            long long sumT = prefT[i] - (j >= 0 ? prefT[j] : 0LL);
            long long strongCost = llabs(sumS - sumT);
            long long candidate = (j >= 0 ? dp[j] : 0LL) + strongCost;
            best = min(best, candidate);
        }

        dp[i] = best;
        setLast(bal, i);
    }

    cout << dp[N - 1] << '\n';
    return 0;
}