[boj] 백준 2565 전깃줄 - dp, 증가하는 수열

[문제]

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

 

[풀이]

왼쪽 전깃줄을 기준으로 정렬했을 때, 오른쪽 전깃줄에서도 똑같이 증가하는 번호만큼 전깃줄이 교차하지 않는다. 

1 8
2 2
3 9
4 1
6 4
7 6
9 7
10 10

예를 들어, 다음과 같이 정렬을 하면, 오른쪽 전깃줄에서는 1, 4, 6, 7, 10 으로 계속 증가하는 형태를 띄므로 최대 5개의 전깃줄이 교차하지 않는다. 즉 8-5=3개의 전깃줄만 자르면 된다.

이는 곧 증가하는 수열 문제로 볼 수 있으므로 dp를 이용해 해결한다. 두번째 줄을 보면 8은 2보다 크므로 증가하는 수열에 포함할 수 없다. 따라서 2 하나만 있으므로 dp 배열에 1을 저장한다. 하지만 세번째 줄의 9는 8보다 크고, 2보다도 크다. 따라서 8과 2에 저장되어있던 1에 1을 더해서 2를 저장한다. 6번째 줄의 6은 2, 1, 4 보다 크다. 이 중 dp 배열에 저장된 가장 큰 값인 2에 1을 더한 4를 저장한다. (즉, 증가하는 수열 1, 4, 6 의 길이인 3만큼이 저장됨.) 

dp 배열에 저장된 가장 큰 값이 교차하지 않는 전깃줄의 최대 개수가 되고, 전체 전깃줄 개수 n에서 뺀 만큼 없애면 된다. 

 

[코드]

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace::std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n; //전깃줄의 개수
    cin >> n;
    int dp[500];
    vector<pair<int, int>> vec;

    for(int i=0; i<n; i++){
        int a, b;
        cin >> a >> b;
        vec.push_back({a, b});
    }

    sort(vec.begin(), vec.end());

    for(int i=0; i<n; i++){
        int cmp = vec[i].second;
        int cnt = 0;
        for(int j=0; j<i; j++){
            if(cmp < vec[j].second)
                continue;
            cnt = max(cnt, dp[j]);
        }
        dp[i] = cnt + 1;
    }

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

    cout << n - answer;

}