백준 2565: 전깃줄(DP)

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

나무위키 최장증가부분수열 사람들이 각각 번호를 가지고 있고 그 번호 순서에 맞춰서 일렬로 정렬하려고 한다. 이때 움직인 사람들의 총 수를 최소로 하고 싶다면 어떻게 해야 하는가? (단, 초기에 사람들은 무작위로 일렬로 섞여 있고, 'A씨, 맨 뒤 / 맨 앞으로 가세요', 'A씨, B씨와 C씨 사이로 가세요' 꼴의 명령으로 사람들을 이동시킨다고 하자.) 이 문제는 전형적인 LIS 응용 문제이다. 움직인 사람들의 총 수가 최소가 된다는 말은 움직이지 않은 사람들의 수가 최대가 된다는 것이다. 사람들의 번호들의 수열에서 이미 오름차순으로 정리된 쌍이 있다면 그들은 움직이지 않아도 된다. 따라서 그 수열의 LIS를 이루는 사람들은 움직이지 않고, 나머지 사람들이 그들 사이로 적절히 배열된다면 정렬할 수 있다.

정렬 -> LIS -> 전깃줄 개수 - 수열 크기

난최고야!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

#include <iostream>
#include <algorithm>
 
struct wire
{
    int A;
    int B;
};
 
wire arr[101];
int dp[101];
 
bool cmp(wire& first, wire& second)
{
    if (first.A < second.A)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> arr[i].A >> arr[i].B;
    }
    std::sort(arr, arr + N, cmp);
    
    int back = 0;
    for (int i = 0; i < N; ++i)
    {
        int it = 0;
        for( ;dp[it] != 0; ++it)
        {
            if (dp[it] > arr[i].B)
            {
                dp[it] = arr[i].B;
                break;
            }
        }
        dp[it] = arr[i].B;
        back = back > it ? back : it;
    }
    std::cout << N - (back + 1);
    return 0;
}

끼에에에에에에에에엒!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!