[C/C++] 백준 2565번 - 전깃줄 (LIS)

 

<LIS 코드>

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

vector<pair<int, int>> v;
int N;
int a, b;
int DP[101];
int tmp = 0;

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> a >> b;
		v.push_back(pair<int, int>(a, b));
	}

	sort(v.begin(), v.end());

	// 가장 긴 증가 수열의 길이 구하는 과정
	DP[0] = 1;
	for (int i = 0; i < N; i++)
	{
		tmp = 0;
		for (int j = 0; j < i; j++)
		{
			// 이전 값들 중에 현재값 보다 작으면서 DP1의 값이 가장 큰 것 찾기.
			if (v[j].second < v[i].second && tmp < DP[j]) tmp = DP[j];
		}
		DP[i] = tmp + 1;

	}

	sort(DP, DP + N, greater<>());
	cout << N - DP[0];

}

 

풀이는 2차원 벡터를 생성한 후 정렬을 한 뒤 v.second들의 값들 중에서 가장 긴 증가수열의 길이를 구하면 전깃줄이 겹치지 않게 만들 수 있는 최대길이 이며, 나머지 전깃줄은 제거해야 전깃줄이 겹치지 않게 된다. 따라서 DP값의 최댓값을 구한 뒤 이것을 입력값에서 빼주면 제거해야 할 전깃줄 개수를 구할 수 있게 된다.

 

 

www.acmicpc.net/problem/2565

2565번: 전깃줄