[BOJ] 2565번: 전깃줄

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2565

2565번: 전깃줄

 

LIS 문제였다.

LIS에 대한 자세한 설명은 아래 글에 있다.

https://hellooworld.tistory.com/21

[BOJ] 11053번: 가장 긴 증가하는 부분 수열

 

단, 배열에 대한 인덱스가 0부터 n까지 차례로 있는게 아니라서

전봇대의 위치 번호의 최대값인 500까지 인덱스로 받을 수 있도록

배열 크기를 501로 설정해주었다.

 

또한 처음에 배열 값은 모두 0으로 설정되어 있고,

전봇대의 위치 번호는 자연수이므로 배열 값이 0인 경우는 A와 B 사이에 전깃줄이 없다는걸 의미한다.

 

전깃줄 개수(n)에서 LIS 길이를 빼주면 우리가 없애야 하는 전깃줄 개수를 구할 수 있다.

 

/*
20200512
baekjoon 2565번 - 전깃줄
*/
#include <iostream>
#include <algorithm>
using namespace std;

int arr[501], dp[501];
int main() {
	cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
	int n, M = 0;
	cin >> n;

	for (int i = 0; i < n; ++i) {
		int idx, val;
		cin >> idx >> val;
		arr[idx] = val;
	}

	for (int i = 1; i <= 500; ++i) {
		if (arr[i] == 0) continue;
		dp[i] = 1;
		for (int j = 1; j < i; ++j) {
			if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
				if (M < dp[i]) {
					M = dp[i];
				}
			}
		}
	}

	cout << n - M;
}