풀이 요약

회의실 문제(그리디) + LIS (DP)

풀이 상세

1. 먼저 겹치지 않게 나올 수 있는 최적해? 를 생각해봐야한다. 전깃줄이 걸리지 않는 조건은 생각보다 단순하다. 이전 전깃줄 $l1$ 과 다음 전깃줄 $l2$ 라고 한다면 $l2$ 의 시작과 끝 인덱스가 $l1$ 의 시작과 끝 인덱스보다 크기만 하면 된다.
2. 각 전깃줄 별 시작과 끝을 저장하자. 나의 경우에는 pair 를 사용했다.
3. 시작 혹은 끝을 기준으로 오름차순 정렬을 하자.
4. 정렬한 값은 어차피 인덱스가 커질 수록 클테니 볼 필요 없고, 정렬시 사용 안한 부분을 수열과 체크하면서 DP 값을 늘려나가자. 그럼 최종적으로 전깃줄이 겹치지 않고 나올 수 있는 최대 증가수열 값이 나온다.
5. 최대 증가수열 값을 총 전깃줄에서 뺀 값이 정답이다.

코드

#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> p;
p a1[104];
int dp[104], N;
bool cmp(p n1, p n2) { return n1.second < n2.second; }
int main() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> a1[i].first >> a1[i].second;
    }

    sort(a1, a1 + N, cmp);
    int ans = 0;
    for (int i = 0; i < N; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a1[j].first < a1[i].first)
                dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(ans, dp[i]);
    }
    cout << N - ans;
}