[백준 / BOJ] C++ 2565 전깃줄

2565번: 전깃줄

 

문제

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

2565번: 전깃줄

 

 

풀이

두 전봇대에 선이 겹치지 않게 가장 많이 연결할 수 있는 전깃줄의 수를 구하는 문제다. 두 전봇대를 A와 B라고 하면 A 전봇대의 연결되는 위치를 기준으로 오름차순으로 정렬한다. 그리고 B 전봇대에 연결되는 위치가 가장 긴 증가하는 부분 수열(LIS)이 되도록 구하면 연결 가능한 전선의 수를 알 수 있다. 전체 전깃줄의 수에서 연결 가능한 전선의 수의 최댓값을 빼면 답을 구할 수 있다.

 

위치의 범위가 500 이하이므로 dp로 해결할 수 있다. LIS는 아래 글을 읽어보면 이해할 수 있다.

https://khyunx.tistory.com/27

[백준 / BOJ] C++ 11053 가장 긴 증가하는 부분 수열

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin >> n;
  vector<pair<int, int>> v(n);
  vector<int> dp(n, 1);
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    v[i] = {a, b};
  }
  sort(v.begin(), v.end());
  for (int i = 0; i < n; i++)
    for (int j = 0; 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()) << '\n';
  return 0;
}