LIS 활용 전기줄

문제 해석

교차되는 전기줄을 없애야한다.
입력을 보면 순서가 정렬되어 나오지 않는다. 따라서 우선 왼쪽 전봇대를 1~n순서로 정렬을 해줘야한다.

연결할 수 있는 최대의 전기줄을 구하면, 반대로 연결 할 수 없는 전기줄 역시 구할 수 있다. 따라서 오른쪽 정렬안된 전봇대에서 가장 긴 부분 수열을 구하고 그 수열을 n에서 빼주면 된다.

정리하자면
1. 왼쪽 입력값을 기준으로 정렬
2. 오른쪽 값들에서 LIS를 구한다.
3. n에서 LIS값을 뺀다

풀이 코드

#include <iostream>
#include <algorithm>
#define MAX 500
using namespace std;

struct Line{
    int left;
    int right;
};

bool compare(Line a, Line b) {
    if (a.left < b.left) return true;
    return false;
}

int n;
Line arr[MAX];
int dp[MAX];

int main() {
    cin >> n;
    fill_n(dp, MAX, 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i].left >> arr[i].right;
    }
    sort(arr + 1, arr + n + 1, compare);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            if (arr[i].right > arr[j].right) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int max_num = 0;

    for (int i = 1; i <= n; i++) {
        max_num = max(dp[i], max_num);
    }

    cout << n - max_num;
}

느낀점

어려운 부분이 두개 있었는데 일단 문제에서 LIS를 써야하는 부분을 찾는점이 조금 어렵고

두번째로를 A를 기준으로 정렬하는 부분이 어렵다.
Python의 경우는 쉽게 a 기준으로 정렬할 수 있는데 cpp나 java의 경우는 따로 boolean 함수를 만들어야 가능하다. 이와 관련해서는 따로 글을 써서 정리하도록 하겠다.