전깃줄

문제 링크

전깃줄이 겹치는 조건이 무엇인지부터 찾아보자. 전깃줄이 출발 위치 인덱스가 증가하면 반드시 도착 위치 인덱스도 함께 증가 해야 한다. 만약 출발 인덱스가 증가했는데 도착인덱스가 증가하지 않으면 전깃줄은 반드시 교차될 수 밖에 없다. 교차하지 않을 수 있는 최대 전깃줄 군집을 먼저 찾고 그 군집에 포함되지 않는 전깃줄이 제거 대상이 된다. 출발 인덱스가 증가함에 따라 도착 인덱스도 증가하는 최대 군집을 찾아야 하는데 출발 인덱스를 배열 인덱스로 두고 도착 인덱스를 배열 값으로 두면 LIS 문제로 치환할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n; cin >> n; vector<int> arr(n + 1), dp(n + 1, 1);
	for(int i=1;i<=n;i++) {
		cin >> arr[i];
	}
	int mx = 0; 
	for(int i=2;i<=n;i++) {
		for(int j=1;j<i;j++) {
			if(arr[i] > arr[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
			}
		}
		mx = dp[i] > mx ? dp[i] : mx;
	}
	cout << n - mx; // 가장 큰 군집에 포함되지 않는 전깃줄 수 출력
	return 0;
}

전깃줄이 겹친다는 명제를 도착 인덱스와 출발인덱스가 모두 증가 한다 라는 명제로 바꾸는게 중요한 문제였다.