백준 2565 전깃줄 c++ // dp, LIS(최장부분증가수열) 풀이

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

2565번: 전깃줄

1. LIS(최장부분증가수열) 풀이

ex) 

수열 / dp값 /해당경우의수

3     / 1      /  3

5     /  2      / 3 5

1     / 1       /1

6      / 3      /3 5 6

4     / 2       /3 4 또는 1 4

일반화 : 앞에서 자기보다 작은게있다 -> 그 dp값 중 최대값 +1

행동영역 : dp문제를 LIS 문제로 해결할수 있을지 시험해보자

 

2. 의사코드

1. first에 대해 정렬후

2. second에 대해 최장부분증가수열 중 최대값을 구하면

그 값이 설치가능한 전깃줄의 최대갯수

3. n-ret == 제거해야하는 전깃줄의 갯수

 

#include <bits/stdc++.h>
using namespace std;

int n, dp[504];
vector<pair<int, int>> v;
vector<int> a;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int a,b;
        cin >> a>>b;
        v.push_back({a,b});
    }

    //1. 좌측기준 정렬
    sort(v.begin(), v.end());
    for (auto p : v) {
        //cout << p.first << " " << p.second << "\n";
        a.push_back(p.second);
    }
    //2. LIS 문제 : 최장부분증가수열 문제로 바뀜
    fill(dp, dp + 504, 1); //초기값 : 1(자기자신부터 시작하면 길이 1임)

    for (int i = 1; i < n; ++i) { //대상
        //뒤에서 자기보다 작은것이 있다면 그중 최대값+1 이 답임.
        priority_queue<int> pq;
        for (int j = i-1; j >= 0; --j) {
            if (a[i] > a[j]) pq.push(dp[j]);
        }
        if (pq.size()) dp[i] = pq.top()+1;
    }

    //for (int i = 0; i < n; ++i) cout << dp[i] << " ";

    //답 : 전체전깃줄갯수 - 설치가능한 최대갯수 == 없애야하는 갯수
    cout << n- *max_element(dp,dp+n);


    return 0;
}