[2565] 전깃줄

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

LIS문제라는 것을 눈치채지 못한 저는 바보입니다.

LIS입니다..

전형적인 DP문제죠...

dp[n] : 인덱스 n까지의 최대 연결 수

라고 정의하면 됩니다.

이렇게 하면 N^2의 시간복잡도로 해결할 수 있습니다.

관련 문제..

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

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

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <string.h>
#include <stack>
#include <cstdio>
 
#define mp make_pair
#define MOD 1000000007
#define INF 0x7fffffff
#define MAX_SIZE (int)1e5
 
using namespace std;
//ios::sync_with_stdio(false); cin.tie(0);
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<bool> vb;
 
int edge[501];
int dp[501];
 
int main() {
    int n;
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
 
        edge[a] = b;
    }
 
    int ret = 0;
 
    for (int i = 1; i <= 500; i++) {
        if (edge[i] == 0) continue;
 
        dp[i] = 1;
 
        for (int j = 1; j < i; j++) {
            if (edge[j] < edge[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
 
        ret = max(ret, dp[i]);
    }
    
    cout << n - ret;
 
    return 0;
}