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

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

2565번: 전깃줄

백준 2565번 전깃줄 문제를 풀었다.

처음에 그리디 방식으로 가장 많이 겹치게 되는 전깃줄을 지우려 했는데 실패하고 다른 사람의 코드를 찾아봤다.

이 문제는 가장 긴 증가하는 부분 수열로 풀 수 있는 문제였다. 입력으로 받은 전깃줄을 A에 대해 오름차순으로 정렬한 뒤에 B를 보면 된다. 문제의 예제를 기준으로 B는 { 8, 2, 9, 1, 4, 6, 7, 10 } 이 된다. 여기서 없애지 않아도 되는 전깃줄의 개수는 B에서 가장 긴 증가하는 부분 수열의 개수가 된다. 이것을 입력으로 받은 N에서 빼면 없애야 하는 전깃줄의 개수가 나오게 된다.

 

아래는 전체 코드입니다.

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

vector<pair<int, int>> line;
int B[101];
int len[101];
int N;

int dp(int n) {
	int LIS = 0;
	for (int i = 0; i < n; i++) {
		len[i] = 1;
		for (int j = 0; j < i; j++) {
			if (B[i] > B[j]) {
				len[i] = max(len[i], len[j] + 1);
				if (LIS < len[i])
					LIS = len[i];
			}
		}
	}
	return LIS;
}

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

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

	for (int i = 0; i < N; i++) {
		B[i] = line[i].second;
	}

	int LIS = dp(N);

	cout << N - LIS;


	return 0;
}