[BAE/<JOON> 문제풀이] 1365. 꼬인 전깃줄

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

1365번: 꼬인 전깃줄

핵심::

주어진 전깃줄 위치들의 LIS(최장 증가 수열)을 구하면 자르지 않아도 되는 가장 긴 전깃줄 묶음을 구할 수 있다.

 

풀이::

LIS를 구하고 전체 전깃줄 수에서 빼면 잘라야하는 최소의 전깃줄 수를 구할 수 있다.

 

의견::

새거 안 배우고 날먹으로 일지 채우는 거 같다. 그래도 1일 1새로운 알고리즘 문제는 에바임 진짜

 

코드::

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

int main()
{
	int n;
	cin >> n; vector<int> arr(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}

	vector<int> dp;
	dp.push_back(arr[1]);
	for (int i = 2; i <= n; i++) {
		if (arr[i] > *(dp.end() - 1)) {
			dp.push_back(arr[i]);
		}
		else {
			auto lb = lower_bound(dp.begin(), dp.end(), arr[i]);
			*lb = arr[i];
		}
	}

	cout << n - dp.size();

	return 0;
}