(2565) 전깃줄

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

단계별로 풀어보기

21단계(동적 계획법 1) 14번째

 

 

 

전깃줄을 A의 위치에 대해 오름차순으로 정렬한다. 이때 전깃줄이 꼬이지 않으려면 B도 오름차순으로 정렬되어 있어야 한다.

따라서 LIS를 구하면 된다. 이때 LIS값은 살릴 수 있는 최대 전깃줄의 수이므로 n에서 최댓값을 빼주면 우리가 원하는 정답이 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<pair<int,int>> v(n+1);
  vector<int> dp(n+1, 1);
  
  for(int i=1;i<=n;i++)  cin >> v[i].first >> v[i].second;
  
  sort(v.begin(), v.end());
  
  for(int i=2;i<=n;i++){
    for(int j=1;j<i;j++){
      if(v[j].second<v[i].second)  dp[i]= max(dp[i], dp[j]+1);
    }
  }
  
  cout << n-*max_element(dp.begin(), dp.end());
  
  return 0;
}