다이나믹프로그래밍1 - 백준 2565번 전깃줄

www.acmicpc.net/problem/2565

2565번: 전깃줄

IDEA

가장 긴 증가하는 부분 수열을 구하는 문제다. 

A전깃줄의 위치 , B전깃줄의 위치 순으로 입력을 받는데 , A전깃줄의 위치에 대해서 오름차순으로 정렬해보면 아래와 같은 그림이 나온다. 

 

왼쪽 A전깃줄번호를 인덱스로 가지는 배열이 있고, 그 값이 B전깃줄번호라고 생각해보자.

[8,2,9,1,4,6,7,10] 이 된다. 이 중 전깃줄이 교차하지 않기 위해서는 i < j 라면 arr[i] < arr[j] 여야한다. 

즉 배열값들이 증가해야된다는 것이다.  최소한의 값만 제거해 증가하는 배열을 만들어야하므로 

 가장 긴 증가하는 부분수열 문제가 된다. 

 

pair vector를 통해 first에는 a전깃줄 second에는 b전깃줄을 받은 후 a를 기준으로 정렬해준다.

b전깃줄의 값 즉 벡터의 second값을 이용하여 대소관계를 판별해 dp값을 채워준다. 

LIS알고리즘 확인은 👉 blahblahlab.tistory.com/79

  

 

CODE

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

vector<pair<int,int>>arr;
int dp[101] = {0};

int main() {
	int n;
	scanf("%d", &n);
	arr.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &arr[i].first, &arr[i].second);
	}
	sort(arr.begin(), arr.end());
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[j].second < arr[i].second) dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	printf("%d", n - *max_element(dp, dp + n + 1));
}