[백준/BOJ] 백준 1365번 : 꼬인 전깃줄

www.acmicpc.net/problem/1365

1365번: 꼬인 전깃줄

가장 긴 증가하는 부분 수열 O(n log n) 알고리즘을 이용하여 문제를 해결했다. 결과는 전체 개수에서 가장 긴 증가하는 부분 수열의 개수를 빼서 구했다

 

코드

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

int n;
vector<int> number;
vector<int> make_long;
vector<int>::iterator it;

//가장 긴 증가하는 부분 수열 O(n log n) 알고리즘을 이용하여 문제를 해결했다
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		number.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		it = lower_bound(make_long.begin(), make_long.end(), number[i]);

		if (it == make_long.end())
			make_long.push_back(number[i]);

		else
			*it = number[i];
	}

	cout << n - make_long.size(); //전체 개수에서 가장 긴 증가하는 부분 수열의 개수를 뺀다

	return 0;
}