전깃줄 - 2( BOJ 2568 )

문제 : https://www.acmicpc.net/problem/2568

2568번: 전깃줄 - 2

 

문제 파악하기

최소한의 전깃줄을 잘라 서로 겹치는 전깃줄이 없게 만드는 문제입니다. 보통 이런 문제는 가장 긴 증가하는 부분 수열(이하 LIS)을 사용하며, 이 문제 역시 대표적인 LIS 문제입니다. 서로 겹치지 않는다는 건 항상 현재 가로등 번호보다 다음 가로등의 번호가 더 커야 한다는 걸 의미하며, 결국 주어진 수열 중 LIS의 길이를 찾는 문제와 동치가 됩니다. 그럼 어떻게 이 문제를 LIS 문제로 바꿀 수 있을까요?

 

문제 해결하기

여기서 중요한 점은 A가로등과 연결된 B가로등의 번호입니다. A가로등은 위치를 의미하며, B가로등은 해당 위치의 값이라고 생각하면 좀 더 쉽게 와닿을 수 있습니다. 예를 들어, 문제에서 주어진 입력 예시는 다음과 같은 수열로 바꿀 수 있습니다.

8 2 9 1 4 6 7 10

 

이렇게 수열로 바꾸면 우리는 어떤 전깃줄을 없애야 하는지 한 눈에 볼 수 있습니다. 바로, 굵게 표시한 전깃줄을 없애면 겹치는 전선이 하나도 없게 됩니다. 이렇게 우리는 주어진 수열 내에서 LIS를 찾은 다음, 출력하는 알고리즘을 설계하면 문제를 해결할 수 있습니다. 여기서 문제점은 LIS를 출력하는 방법인데, 이 경우에는 세그먼트 트리를 사용하면 손쉽게 출력할 수 있습니다.

 

LIS를 구할 때, 가장 중요한 요소는 바로 나보다 왼쪽에 위치한 작은 숫자 중 LIS 길이가 최대가 되는 값입니다. 그럼 우리는 2가지, 즉 나보다 '작은 숫자'와 'LIS 길이가 최대'가 되는 요소를 탐색해야 하며, 보통 이런 경우에는 2중 반복문을 사용합니다. 하지만 이 문제에서 N의 값은 최대 100,000이기 때문에 시간 복잡도 상 중첩 반복문을 사용하는 건 불가능합니다. 그렇기에 우리는 여기서 새로운 도구가 필요하며, 정렬과 세그먼트 트리는 문제를 해결하는데 핵심적인 도구입니다. 우선, 입력된 숫자들을 원래 자리의 위치를 기록한 상태로 정렬합니다. 그럼 위의 수열은 다음과 같은 모습으로 바뀌게 됩니다.

1(4) 2(2) 4(5) 6(6) 7(7) 8(1) 9(3) 10(10)

 

그리고 이 순서대로 세그먼트 트리에 삽입하면 됩니다. 삽입하기 전, 자신의 왼쪽을 살펴보면서 LIS의 최댓값을 탐색한 다음, 지금까지의 LIS 길이와 이전에 참고한 숫자의 위치를 기록하면 됩니다. 이렇게 정렬과 세그먼트 트리를 사용하면 위에서 설명한 2가지 요소를 한 번에 처리할 수 있습니다. 우선, 정렬했기 때문에 자신의 왼쪽에 먼저 들어온 숫자들은 항상 자신보다 작은 숫자들입니다. 이 중에서 LIS 길이의 최댓값은 세그먼트 트리를 사용하면 빠르게 구할 수 있습니다. 이렇게 세그먼트 트리를 구한 다음에는 별도의 탐색을 거치면서 LIS 길이에 포함되는지 확인하는 과정을 거치면 문제를 해결할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <string.h>
#include <utility>
#include <vector>
#include <algorithm>
#define NMAX 100010
#define MMAX 500010
#define PAIR pair<int, int>
using namespace std;
 
int N;
int a, b;
vector< PAIR > inp, convertInp;
 
int sz;
PAIR curMax, vmax;
PAIR segTree[NMAX*4];
 
int idx;
int lis[NMAX][2], used[NMAX];
int convertA[MMAX];
 
void update(int k) {
    while(k>0) {
        segTree[k] = max(segTree[k*2], segTree[k*2+1]);
        k /= 2;
    }
}
 
PAIR search(int l, int r) {
    PAIR ret={0,0};
 
    while(l<=r) {
        if(l%2==1) {
            if(ret.first < segTree[l].first) ret = segTree[l];
            l++;
        }
        if(r%2==0) {
            if(ret.first < segTree[r].first) ret = segTree[r];
            r--;
        }
 
        l/=2; r/=2;
    }
 
    return ret;
}
 
void dfs(int idx, int cnt) {
    if(cnt == 0) return;
 
    used[idx] = 1;
    dfs(lis[idx][1], cnt-1);
}
 
int main() {
    scanf("%d", &N);
    for(int i=0;i<N;i++) {
        scanf("%d %d", &a, &b);
        inp.push_back({a, b});
    }
 
    // inp은 A가로등 기준으로 정렬
    sort(inp.begin(), inp.end());
 
    // convertInp은 B가로등 기준으로 정렬
    for(int i=0;i<N;i++) convertInp.push_back({inp[i].second, i});
    sort(convertInp.begin(), convertInp.end());
 
 
    // 세그먼트 트리로 lis 탐색
    for(sz=1;sz<N;sz*=2);
    memset(lis, -1, sizeof(lis));
 
    for(int i=0;i<N;i++) {
        curMax = search(sz, convertInp[i].second+sz);
 
        lis[convertInp[i].second][0] = curMax.first+1;
        lis[convertInp[i].second][1] = curMax.second;
        vmax = max( vmax, make_pair(curMax.first+1, convertInp[i].second) );
 
        segTree[convertInp[i].second+sz] = make_pair(curMax.first+1, convertInp[i].second);
        update((convertInp[i].second+sz)/2);
    }
 
    // lis에 포함된 가로등 체크
    dfs(vmax.second, vmax.first);
 
    // lis에 해당하지 않은 가로등 출력
    printf("%d\n", N-vmax.first);
    for(int i=0;i<N;i++) {
        if(!used[i]) printf("%d\n", inp[i].first);
    }
}

후기

세그먼트 트리를 사용한 LIS 탐색 기법은 웰-노우 문제라고 생각합니다. 다만, 문제를 구현하는데 헷갈리는 요소가 있어서 확실한 알고리즘 설계가 중요하다는 걸 느끼게 되었습니다. LIS를 공부하는 사람에게 추천하고 싶은 문제입니다.