Aliens Trick

Aliens Trick, WQS Binary Search, Lagrange Optimization, 에일리언 트릭

정의

Aliens Trick (또는 WQS Binary Search, Lagrange Optimization) 은 “정확히 K 개 선택” 같은 까다로운 제약을 가진 DP 를, 제약을 lambda 페널티로 완화 한 자유 DP + 외부 이분탐색으로 푸는 기법.

IOI 2016 의 “Aliens” 문제에서 유명해져서 이름이 붙었다. 한국식 이름은 “외계인 트릭”. Slope Trick 과 함께 DP 의 볼록성 을 활용하는 대표적인 최적화.

문제 상황과 동기

왜 필요한가

“N 개 중 정확히 K 개를 선택해 비용 최소화” 는 직관적인 DP 상태로 dp[i][k] = i 까지 봤고 k 개 선택한 최소 비용 이다. 전이는 O(N), 상태는 O(NK), 전체 O(N² K) 또는 O(NK²).

N=10^5, K=10^5 일 때 10^10 연산, 시간 초과.

Naive 해법의 한계: K 차원을 명시적으로 들고 가면 상태 공간이 폭발한다.

Aliens Trick 의 돌파구: DP 가 K 에 대해 볼록 (convex or concave) 하면, K 제약을 제거하고 “선택할 때마다 페널티 λ 를 부과” 하는 무제약 DP 를 푼다. 이 DP 는 O(N) 또는 O(N log N). λ 를 이분탐색해 정확히 K 개를 선택하게 만든다. 전체 O(N log V) 또는 O(N log N log V).

10^5 → 10^5 * log(10^6) ≈ 2*10^6, 통과.

전형적 문제

• “N 개 선분 중 K 개를 선택해 덮는 면적 최대화”
• “K 개 그룹으로 나눠 각 그룹 비용의 합 최소화”
• “K 번의 연산으로 배열을 정렬하는 최소 비용”

시각화

핵심 아이디어

원 문제: f(K) = K 개를 선택할 때 최대 / 최소 비용.

DP 가 K 의 함수로 볼록 (concave / convex) 하면, K 제약을 제거 하고 선택할 때마다 페널티 λ 를 부여 한 자유 DP g(λ) = max (f(K) - λK) 를 정의. 이 g 는 K 가 자유롭게 정해진 무제약 DP.

g(λ) = max_K (f(K) - λK)

이는 함수 f(K) + λK 의 위쪽 봉투 (upper envelope) 의 점이다. λ 를 키울수록 g 의 argmax 인 K(λ) 는 단조 감소 (또는 증가). 따라서 λ 에 대해 이분탐색 으로 원하는 K 를 정확히 맞출 수 있다.

핵심 불변량: f(K) 가 K 에 대해 볼록하면 f(K) - λK 의 최댓값을 주는 K 는 λ 가 증가할수록 감소한다 (또는 증가, 부호에 따라). 이 단조성이 이분탐색을 가능하게 한다.

def solve(K):
    lo, hi = 0, MAX_LAMBDA
    while lo < hi:
        mid = (lo + hi) // 2
        chosen, value = solve_unconstrained(lambda=mid)
        if chosen >= K: lo = mid + 1
        else:           hi = mid - 1
    # lambda 에 따라 K 가 정확히 일치하지 않을 수 있음, 끝에서 보정
    return solve_unconstrained(lambda=lo).value + lo * K

구현

아래는 골격 코드. 실제 문제에 맞춰 solve_unconstrained 의 DP 전이를 채워 넣는다.

// O(N log V) 또는 O(N log N log V) (무제약 DP 가 O(N log N) 이면 후자)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// lambda 페널티 하에서 무제약 DP
// 반환: {비용 (페널티 포함), 선택 개수}
pair<ll, int> solve_unconstrained(ll lambda) {
    // 예: dp[i] = i 까지 봤을 때 최소 비용 (선택할 때마다 -lambda)
    // 실제 전이는 문제마다 다름
    // 여기서는 골격만
    ll cost = 0; // 페널티 포함 비용
    int count = 0; // 선택한 개수
    // ... DP 전이 ...
    return {cost, count};
}

// 정확히 K 개를 선택하는 최소 비용
ll solve_with_k(int K) {
    ll lo = -1e9, hi = 1e9; // lambda 범위는 문제마다 조정
    while (lo < hi) {
        ll mid = (lo + hi) / 2;
        auto [cost, cnt] = solve_unconstrained(mid);
        if (cnt >= K) lo = mid + 1; // 더 많이 선택, lambda 증가
        else hi = mid - 1;
    }
    auto [final_cost, final_cnt] = solve_unconstrained(lo);
    // 보정: 실제 비용 = (페널티 포함 비용) + lambda * K
    return final_cost + lo * K;
}

int main() {
    int N, K;
    cin >> N >> K;
    // ... 입력 ...
    cout << solve_with_k(K) << "\n";
}

구현 팁

1. lambda 범위: 비용의 절댓값 최댓값으로 설정. 너무 좁으면 답을 못 찾음.
2. tie-break: 같은 비용일 때 K 큰 쪽 / 작은 쪽 우선순위를 일관되게.
3. 부호 주의: 최대화는 concave, 최소화는 convex. 부등호와 페널티 부호를 맞춰야 함.

전제 조건

볼록 / 오목 (convex / concave in K) 이 핵심. f(K) 가 볼록이면 페널티 λK 를 더한 함수는 위로 볼록의 봉투 = 단조성 보장.

볼록 조건: f(K+1) - f(K) 가 K 에 대해 단조 (감소/증가)

볼록이 아니라면 Aliens Trick 적용 불가, 다른 방법 (Knuth Optimization, DnC, Slope Trick 등) 을 고려.

복잡도

항목	값
Unconstrained DP 1 회	O(N) 또는 O(N log N)
λ 이분탐색	O(log V) (V = 페널티 값 범위)
전체	O(N log V) 또는 O(N log N log V)

원래 O(N²), O(NK²) 였던 DP 를 한 단계 낮춰 준다.

함정

1. K 가 정확히 안 맞는 경우

f 의 그래프 위에 정확히 (K, f(K)) 점이 평면에 끼이지 않으면 (collinear 한 점들이 있는 경우) 이분탐색 결과 K(λ) 가 목표 K 를 건너뛴다. 답 보정식: g(λ) + λK.

2. 정수 λ 일 때 동률 처리

여러 K 가 같은 f(K) - λK 값을 줄 수 있다. unconstrained DP 에서 최대 K 를 선호 하도록 tie-break 를 일관되게 둬야 한다.

3. 역추적 (선택한 원소 복원)

마지막 λ 로 unconstrained DP 를 한 번 더 돌리며 backtrack. 단순 값 계산보다 코드가 길다.

4. concave 인지 convex 인지 헷갈림

최대화 문제는 concave (위로 볼록) 이어야 함. 최소화는 convex (아래로 볼록). 부호와 부등호 방향을 끝까지 일관되게.

Slope Trick 과의 차이

항목	Aliens Trick	Slope Trick
다루는 것	f(K) 의 한 점	f(x) 함수 전체
핵심 도구	외부 이분탐색 + 일반 DP	두 개 priority queue
제약 종류	”정확히 K 개”	piecewise-linear 페널티
결과	단일 값	전체 함수

둘 다 볼록성을 활용하지만 다루는 방향이 직교적. 같은 문제를 두 방법 다 풀 수 있는 경우도 있고, 한 쪽만 풀리는 경우도 많다.

BOJ 연습 문제

최적값 구하기

번호	제목	링크
BOJ 19672	Feast	kokoa-lab
BOJ 20090	Aliens (IOI 2016)	kokoa-lab
BOJ 14510	Blazing New Trails	kokoa-lab
BOJ 17439	꽃집	kokoa-lab

역추적

번호	제목	링크
BOJ 18456	Jealous Split	kokoa-lab

다른 출처 연습 문제

출처	제목	링크
Codeforces	Edu Round 79 F	https://codeforces.com/contest/1279/problem/F

참고

• Slope Trick
• 볼록 다각형 접선 최적화