[백준 / C++] 2565번: 전깃줄 (LIS 응용)

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

2565번: 전깃줄

난이도: solved.ac 골드 5

 

알고리즘 분류

다이나믹 프로그래밍, LIS

 

접근 방법

전깃줄이 겹치지 않으려면 A 전봇대에서 이어지는 B 전봇대의 번호가 오름차순이어야 한다.

따라서 자르는 전깃줄의 개수를 최소화하려면 LIS를 찾아야 한다.

가장 긴 증가하는 부분 수열만을 남기고 나머지는 다 잘라버려야 한다.

 

구현

LIS 알고리즘 사용해서 (11053번 포스팅 코드 참고) 가장 긴 수열의 길이를 구하고 N에서 그 길이를 빼면 자르는 전깃줄의 개수를 알 수 있다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, a, b, i, j;
	vector<pair<int, int>> line;
	int lis[100];
	cin >> N;
	for (i = 0; i < N; i++) {
		cin >> a >> b;
		line.push_back(make_pair(a, b));
	}
	sort(line.begin(), line.end());
	int Max = 0;
	for (i = 0; i < N; i++) {
		lis[i] = 1;
		for (j = 0; j < i; j++) {
			if (line[i].second > line[j].second)
				lis[i] = max(lis[i], lis[j] + 1);
		}
		if (lis[i] > Max)
			Max = lis[i];
	}
	cout << N - Max;
}

 

성능

코드 제출 결과