[C++/LIS] 백준 2565 전깃줄

문제풀이

LIS를 이용해 푼다.

• 전깃줄이 겹치지 않으려면
  두 전선이 있을 때,
  한 전선의 (1)시작 위치가 다른 전선의 시작 위치보다 크며(인덱스가 크며),
  (2)끝 위치가 다른 전선의 끝 위치보다 커야한다.
  (예, 1-2, 2-4, 3-9 등...)

1. 전깃줄 정렬
   전깃줄은 시작 위치와 끝 위치가 있는데
   시작 위치에 대한 조건을 고정하기 위해
   시작 위치를 기준으로 정렬한다.
   정렬 후 (1)시작 위치가 다른 전선의 시작 위치보다 커야 한다는 조건이 충족된다
   예)
   8
   1 8
   2 2
   3 9
   4 1
   6 4
   7 6
   9 7
   10 10

2. LIS 구하기
   정렬 후 LIS를 구하면
   (2)끝 위치가 다른 전선의 끝 위치보다 커야 한다는 조건을 충족시키는 것이므로
   정렬 후 끝 위치에 대한 LIS를 구한다.
   LIS를 구하는 과정은 https://deonggideok.tistory.com/25에 설명되있다.
   1 8
   2 2
   3 9
   4 1
   6 4
   7 6
   9 7
   10 10
   이 때의 LIS는 (2,4,6,7,10), (1,4,6,7,10)이다.

3. 결과 구하기
   LIS 길이는 전선을 없앴을때, 교차하지 않는 전선들의 최대 개수와 같으므로
   전체 전선 개수 - LIS 길이가 없애야하는 전깃줄의 최소 개수다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
    int n; // 전깃줄 개수
    cin >> n;
    vector<pair<int, int>> v; // 전깃줄 담을 백터
 
    // 전깃줄 정보 입력
    for (int i = 0; i < n; i++) {
        int start, end;
        cin >> start >> end;
        v.push_back({ start, end });
    }
 
    sort(v.begin(), v.end()); // 시작 위치를 기준으로 전깃줄 정렬
 
    // LIS 구하기
    int dp[501]; // DP 결과 저장 배열
    int maxDP = 0; // LIS 길이
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (v[i].second > v[j].second) { // 증가하는 부분수열이 가능한 경우
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxDP = max(maxDP, dp[i]);
    }
 
    cout << n - maxDP << endl; // 전체 전깃줄에서 LIS 길이를 뺀 것이 최소 줄일 수 있는 전깃줄 개수
}