[Algorithm] Baekjoon 2565번 : 전깃줄

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

2565번: 전깃줄

struct Node
{
    int num;
    int toNum;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.num < b.num;
}
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    vector<Node> v;
    int dp[501] = { 0 };
    int arr[501] = { 0 };
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
 
        v.push_back({ a,b });
    }
 
    sort(v.begin(), v.end(),cmp);
 
    for (int i = 0; i < v.size(); ++i)
    {
        arr[i] = v[i].toNum;
    }
    
    int answer = 0;
 
    for (int i = 0; i < n; ++i)
    {
        dp[i] = 1;
        int maxNum = 0;
 
        for (int j = 0; j < i; ++j)
        {
            if (arr[j] < arr[i])
            {
                maxNum = max(maxNum, dp[j]);
            }
        }
 
        dp[i] += maxNum;
        answer = max(answer, dp[i]);
    }
 
    cout << n - answer;
 
    return 0;
}

 

문제는 삭제해야할 전깃줄의 최소개수를 구해야 하지만, 역으로 생각하면 쉽게 풀 수 있는 문제이다.

역으로 생각하면 올바른 형태의 최대전깃줄 개수를 구하는 문제가 되고, 이 형태는 결국 가장 긴 증가하는 부분수열을 구하는 문제가 된다.