교차하지 않는 다리 건설 문제

강의 양안에 위치한 도시들을 연결하는 다리를 건설할 때 교차하지 않도록 최대 다리 수를 구하는 문제입니다. 하안 도시를 배열 인덱스로, 상안 도시 번호를 값으로 매핑하면 최장 증가 부분 수열(LIS) 문제로 변환됩니다. 도시 쌍을 정렬한 후 LIS 길이를 계산합니다.

#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 5005;
typedef pair<int, int> CityPair;

CityPair cities[MAX_N];
int dp[MAX_N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> cities[i].first >> cities[i].second;
    }
    sort(cities, cities + n);
    
    int max_bridges = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (cities[i].second > cities[j].second) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_bridges = max(max_bridges, dp[i]);
    }
    cout << max_bridges;
    return 0;
}

최대 합 증가 부분 수열

기본 LIS 문제를 변형하여 증가 부분 수열의 최대 합을 구합니다. 각 위치에서 이전 작은 값들의 최대 합을 누적하며 계산합니다.

int main() {
    int n;
    cin >> n;
    int arr[MAX_N], dp_sum[MAX_N];
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    int max_total = 0;
    for (int i = 0; i < n; i++) {
        dp_sum[i] = arr[i];
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                dp_sum[i] = max(dp_sum[i], dp_sum[j] + arr[i]);
            }
        }
        max_total = max(max_total, dp_sum[i]);
    }
    cout << max_total;
    return 0;
}

트리 구조를 활용한 고속 LIS 계산

대규모 데이터 처리 시 이진 인덱스 트리(Fenwick Tree)로 최대 합 LIS를 최적화합니다. 좌표 압축을 적용해 값의 범위를 축소합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAX = 100010;

int arr[MAX];
LL fenwick[MAX];
vector<int> comp_vec;
LL dp_val[MAX];

int compress(int val) {
    auto it = lower_bound(comp_vec.begin(), comp_vec.end(), val);
    return distance(comp_vec.begin(), it) + 1;
}

int lowbit(int x) { return x & -x; }

void update(int idx, LL v) {
    for (int i = idx; i <= comp_vec.size(); i += lowbit(i))
        fenwick[i] = max(fenwick[i], v);
}

LL query(int idx) {
    LL ret = 0;
    for (int i = idx; i > 0; i -= lowbit(i))
        ret = max(ret, fenwick[i]);
    return ret;
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        comp_vec.push_back(arr[i]);
    }
    sort(comp_vec.begin(), comp_vec.end());
    comp_vec.erase(unique(comp_vec.begin(), comp_vec.end()), comp_vec.end());
    
    LL result = 0;
    for (int i = 0; i < n; i++) {
        int comp_idx = compress(arr[i]);
        dp_val[i] = query(comp_idx - 1) + arr[i];
        result = max(result, dp_val[i]);
        update(comp_idx, dp_val[i]);
    }
    printf("%lld\n", result);
    return 0;
}

최소 증가 부분 수열을 이용한 시퀀스 커버

주어진 수열을 최소 개수의 증가 부분 수열로 분할하는 문제입니다. 그리디 접근법으로 각 수열의 마지막 값을 추적하며 새로운 그룹을 생성합니다.

int main() {
    int n;
    cin >> n;
    int seq[MAX], last_vals[MAX];
    for (int i = 0; i < n; i++) cin >> seq[i];
    
    int group_cnt = 0;
    for (int i = 0; i < n; i++) {
        int pos = 0;
        while (pos < group_cnt && last_vals[pos] < seq[i]) 
            pos++;
        last_vals[pos] = seq[i];
        if (pos >= group_cnt) 
            group_cnt++;
    }
    cout << group_cnt;
    return 0;
}