[백준] 2565번 C++ 전깃줄

 

문제:https://www.acmicpc.net/problem/2565

 

풀이)

이 문제는 전깃줄이 겹치는 안된다는 점에서 해결법을 찾을 수 있다.

전깃줄이 겹치지 않는 상태에서 없애야하는 전깃줄의 최소개수를 구하려면

전깃줄이 최대가 되는 상태를 구하면 된다. 따라서 오른쪽 전봇대를 보면, 

1->8

3->9

2->2

4->1

6->4

10->10

9->7

7->6

이것을 순서대로보면 {8,2,9,1,4,6,7,10}이 되며 여기서 증가하는 수열이 가장 긴 것을 고르면 {1,4,6,7,10}이된다.

따라서 총 전선개수 8개에서 전선이 최대일때의 개수 5를 빼주면 

없애야하는 전깃줄의 최소개수를 구할 수 있다. 

 

코드)

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

int main()
{
	int n;
	cin >> n;

	vector<int> v(501,0);
	vector<int> v2;


	for (int i = 0; i < n; ++i) {
		int x, y;
		cin >> x >> y;
		v[x] = y;
	}

	for (int i = 0; i < 501; ++i) {
		if (v[i] != 0) {
			v2.push_back(v[i]);
		}
	}


	vector<int> lis(n,1);

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			if (v2[j] < v2[i]) {
				lis[i] = max(lis[i], lis[j] + 1);
			}
		}
	}

	int max_cnt = *max_element(lis.begin(), lis.end());

	cout << n - max_cnt;

}