Slope Trick

Slope Trick, slope-trick, 기울기 트릭

정의

Slope Trick (기울기 트릭) 은 볼록 (convex) 한 piecewise-linear 함수 를 DP 상태값으로 들고 갈 때, 함수 전체를 메모리에 펼치지 않고 꺾이는 지점 (breakpoint) 만 두 개의 우선순위 큐로 유지 해 전이 비용을 O(log N) 으로 떨어뜨리는 DP 최적화 기법.

전형적인 응용은 “각 단계에서 값을 자유롭게 +/- 조정할 수 있고, 그 조정량의 절댓값 합을 최소화” 하는 문제. CHT (Convex Hull Trick), Aliens Trick 와 함께 PS 의 볼록성 (convexity) 을 활용하는 3대 DP 최적화 로 묶인다.

문제 상황과 동기

왜 필요한가

DP 에서 상태값이 단일 숫자가 아니라 함수 전체 일 때가 있다. 예를 들어 “각 단계에서 값을 임의로 조정할 수 있고, 조정량 합을 최소화” 하는 문제:

f_i(x) = (i 번째 단계까지 왔고 현재 값이 x 일 때 최소 비용)

x 의 범위가 10^9 라면 배열로 들고 다닐 수 없다 (O(NV) 메모리, 불가능).

Naive 접근: 모든 x 에 대해 f_i(x) 를 계산, O(NV) 시간과 공간. V=10^9 이면 불가능.

Slope Trick 의 돌파구: f_i(x) 가 piecewise-linear 이고 볼록 하면, 함수 전체를 저장할 필요 없이 꺾이는 지점만 두 개의 우선순위 큐 (max-heap L, min-heap R) 로 유지한다. 전이 한 번당 O(log N), 전체 O(N log N).

전형적 문제

• “수열 a 를 단조 비감소 수열 b 로 바꾸는 최소 비용 Σ|a_i - b_i|”
• “N 단계, 각 단계에서 값을 ±1 조정 가능, 목표값에 가까워지는 최소 비용”
• “트리 DP 에서 각 노드의 값을 조정해 부모-자식 합 제약을 만족시키는 최소 비용”

공통점: 비용 함수가 절댓값 |x-a| 의 합으로 표현되고, 이는 piecewise-linear convex 함수다.

시각화

핵심 아이디어

DP 함수 f_i(x) 가 다음 두 성질을 만족한다고 하자.

1. piecewise-linear: 기울기가 정수인 직선 조각들로 이루어진다.
2. convex: 기울기가 단조 증가 (-∞ 에서 +∞ 로).

이런 함수는 다음 셋만으로 완벽히 표현된다.

• 최솟값 min_f
• 최솟값을 만드는 구간의 왼쪽 breakpoint 들 L (큰 값이 위에 오는 max-heap)
• 최솟값을 만드는 구간의 오른쪽 breakpoint 들 R (작은 값이 위에 오는 min-heap)

함수 평가는 안 한다. 연산이 들어올 때마다 두 힙을 갱신 한다.

핵심 불변량: L 의 최댓값 ≤ R 의 최솟값. 최솟값 구간은 [L.top(), R.top()]. 이 구간 밖에서는 기울기가 음수 (왼쪽) 또는 양수 (오른쪽) 로 선형 증가.

f(x)
  \         /
   \      /
    \   /
     \_/_______   <- 최솟값 구간 [L.top, R.top]
     L|  |R
breakpoint    breakpoint

예제 추적

f(x) = 0 에서 시작, |x-3| 과 |x-1| 을 차례로 더한다.

초기: f(x) = 0, L=[], R=[], min_f=0

f(x) += |x-3|:
  L.push(3), R.push(3)
  L.top()=3 > R.top()=3 ? 아니므로 통과
  L=[3], R=[3], min_f=0

f(x) += |x-1|:
  L.push(1), R.push(1)
  L.top()=3 > R.top()=1 ? 예, 교환 필요
  l=3 pop, r=1 pop, L.push(1), R.push(3)
  min_f += 3-1=2
  L=[1,1], R=[3,3], min_f=2

최종 f(x) = |x-3| + |x-1|, 최솟값 2 at x∈[1,3]

기본 연산

1. f(x) += |x - a|

값을 a 로 끌어당기는 페널티를 더한다. 이게 Slope Trick 의 본질적인 한 수.

L.push(a)
R.push(a)
if L.top() > R.top():
    l = L.pop(), r = R.pop()
    L.push(r)
    R.push(l)
    min_f += l - r

새로 들어온 a 가 현재 최소 구간의 왼쪽이면 R 쪽으로, 오른쪽이면 L 쪽으로 흘려보낸다. 흘려보낸 만큼 최솟값이 증가.

2. f(x) += max(0, x - a) 또는 f(x) += max(0, a - x)

한쪽만 더하는 경우. R 쪽에만 push 하면 된다 (기울기가 한쪽만 1 증가).

3. f(x) = min_{y <= x or y >= x} f(y)

평탄화 (prefix/suffix min). 한쪽 힙을 비우면 된다.

4. shift

f(x) → f(x - c). 두 힙 모두 c 만큼 더한다 (lazy 로 offset 만 들고 다님).

시간 복잡도

연산	비용
|x - a| 추가	O(log N)
평탄화	O(1) amortized
평행이동	O(1) (offset lazy)
최솟값 / breakpoint 조회	O(1)

전체 N 개의 step 으로 이루어진 DP 는 O(N log N).

구현

다음은 Slope Trick 자료구조의 골격. |x-a| 추가, 평탄화, shift 를 지원한다.

// O(log N) 전이, O(N) 공간 (볼록 piecewise-linear 함수를 두 PQ 로 유지)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SlopeTrick {
    priority_queue<ll> L; // max-heap, 왼쪽 breakpoint
    priority_queue<ll, vector<ll>, greater<ll>> R; // min-heap, 오른쪽
    ll min_f; // 최솟값
    ll offset_L, offset_R; // lazy shift

    SlopeTrick() : min_f(0), offset_L(0), offset_R(0) {}

    // f(x) += |x - a|
    void add_abs(ll a) {
        a -= offset_L; // lazy 보정
        L.push(a);
        a = L.top(); L.pop();
        a += offset_L - offset_R;
        R.push(a);
        if (!R.empty() && L.top() + offset_L > R.top() + offset_R) {
            ll l = L.top() + offset_L; L.pop();
            ll r = R.top() + offset_R; R.pop();
            L.push(r - offset_L);
            R.push(l - offset_R);
            min_f += l - r;
        }
    }

    // f(x) = min_{y <= x} f(y) (왼쪽 평탄화)
    void flatten_left() {
        while (!R.empty()) R.pop();
    }

    // f(x) = min_{y >= x} f(y) (오른쪽 평탄화)
    void flatten_right() {
        while (!L.empty()) L.pop();
    }

    // f(x) -> f(x - c) (전체 shift)
    void shift(ll c) {
        offset_L += c;
        offset_R += c;
    }

    ll get_min() const { return min_f; }
};

int main() {
    int N;
    cin >> N;
    SlopeTrick st;
    for (int i = 0; i < N; i++) {
        ll a; cin >> a;
        // 예: BOJ 13323, a_i -= i 치환 후
        st.add_abs(a);
        st.flatten_left(); // non-decreasing 제약
    }
    cout << st.get_min() << "\n";
}

구현 팁

1. lazy offset: shift 연산을 두 힙 전체에 적용하지 않고 offset 변수로만 관리.
2. 평탄화 주의: flatten_left 는 R 비우기, flatten_right 는 L 비우기. 헷갈리면 그림 그려 확인.
3. 초기화: f(x) = 0 은 L=[], R=[], min_f=0 으로 표현.

전형적 문제 유형

• 수열 b 를 단조 증가하게 만드는 최소 비용 (각 원소를 ±k 변경, 합 최소화)
• 두 수열의 EMD (Earth Mover’s Distance) 류 매칭
• 트리에서 각 노드의 가중치를 적절히 옮겨 자식 합 제약을 만족시키는 최소 비용
• 공장/창고 배치 1차원 문제

예제: BOJ 13323 수열 1

N 개의 수열 a 를 strictly increasing b 로 바꿀 때 Σ |a_i - b_i| 최소화

전이: 시점 i 에서 f_i(x) = (이전 단계 i-1 의 함수에 x 까지 도달 가능) + |a_i - x|. x 는 b_i 의 후보.

strictly increasing 제약은 b_i ≥ b_{i-1} + 1 이므로 시점마다 a_i := a_i - i 로 치환하면 b_i ≥ b_{i-1} 의 non-decreasing 문제가 된다 (표준 변환).

Slope Trick 으로 한 step 마다:

1. f_i(x) := min_{y ≤ x} f_{i-1}(y) (평탄화)
2. f_i(x) += |a_i - x| (페널티 추가)

전체 O(N log N).

함정

1. 볼록성 깨지는 전이는 사용 불가

f(x) := f(x) * 2 처럼 곱하기 / 비선형 변환은 piecewise-linear 가 아니라서 Slope Trick 적용 불가.

2. 절댓값이 아닌 quadratic 페널티

|x-a| 가 아니라 (x-a)^2 면 함수는 볼록하지만 piecewise-linear 가 아닌 piecewise-quadratic. 이 경우 BBST 기반 다른 자료구조 (예: persistent treap) 가 필요.

3. 강한 단조 조건의 치환

위의 a_i -= i 같은 치환을 빼먹으면 답이 틀린다. strictly 와 non-decreasing 변환은 Slope Trick 문제의 단골 함정.

4. 평탄화 방향

prefix min 인지 suffix min 인지 헷갈리면 결과가 완전히 다른 함수가 된다. R 을 비우면 prefix min (왼쪽 무한 평평), L 을 비우면 suffix min.

다른 볼록 DP 최적화와의 관계

기법	다루는 양	핵심 자료구조
Slope Trick	piecewise-linear convex function	두 개 priority queue
Convex Hull Trick	직선들의 lower/upper envelope	sorted vector or Li Chao Tree
Aliens Trick	“K 개 선택” 제약을 lambda 로 풀기	외부 이분탐색 + 일반 DP
DnC Optimization	분할 정복 DP	재귀

세 가지 모두 DP 함수의 볼록성 을 활용하지만 다루는 방식이 다르다. 함수 자체를 명시적으로 들고 갈 때가 Slope Trick.

BOJ 연습 문제

번호	제목	링크
BOJ 13323	BOJ 수열 1	kokoa-lab
BOJ 18720	Bookface	kokoa-lab
BOJ 19693	Safety	kokoa-lab
BOJ 12736	Fireworks	kokoa-lab

참고

• Aliens Trick
• Berlekamp-Massey
• 정렬 알고리즘