[문제풀이] 백준 2565 - 전깃줄

📢 문제

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

📢 알고리즘

DP(동적 계획법)

📢 풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

pair<int, int> arr[101]; //전기줄 정보
int DP[101];             // i를 포함하는, i번째 수까지의 부분증가수열 최대 길이

int main()
{
  int N;             //전기줄 개수
  int maxIncLen = 0; // second 기준 증가하는 부분수열 최대 길이
  cin >> N;
  for (int i = 1; i <= N; i++)
  {
    cin >> arr[i].first >> arr[i].second;
  }

  //오름차순 정렬
  sort(arr + 1, arr + N + 1);

  // N - second 기준 증가하는 부분수열의 최대길이
  arr[0] = make_pair(0, 0);
  for (int i = 1; i <= N; i++)
  {
    int max = 0;
    for (int j = 0; j < i; j++)
    {
      if (arr[i].second > arr[j].second && max <= DP[j])
      {
        max = DP[j];
      }
    }
    DP[i] = max + 1;
    if (DP[i] > maxIncLen)
    {
      maxIncLen = DP[i];
    }
  }

  cout << N - maxIncLen;
}

• 전깃줄이 겹친다 = arr[i].first < arr[i+1].first && arr[i].second > arr[i+1].second

• first 기준으로 오름차순 정렬하면 second만 봐도 겹치는지 여부를 알 수 있음

• second만 봤을 때, 증가하면 겹치지 않는 것, 감소하면 겹치는 것

• 따라서 N - second 기준 증가하는 부분수열의 최대길이
  = 모든 전깃줄이 겹치지 않도록 하기 위해 제거하는 전깃줄 최소 개수

DP문제... 잠시 하산합니다.. 다른거 공부하자^^..