BOJ)2565 전깃줄 / LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

LIS의 기본적인 예를 들어보이자면,

8 2 9 1 4 11 6 7 5 10 의 수열이 주어졌을 때,

8 2 9 1 4 11 6 7 5 10    혹은

8 2 9 1 4 11 6 7 5 10 

를 나타내는 것이다.

1. 앞에서 부터, 순차적으로 수를 선택하여 나갈 때,

2. 수는 증가하여야 하며,

3. 그 선택되어진 숫자가 가장 많은 경우를 찾는 것이다.

void LIS() { lis[0] = 1; for (int i = 1; i <= n; i++) { lis[i] = 1; for (int j = 1; j < i; ++j) { if (arr[j] < arr[i] && lis[j] + 1 > lis[i]) { lis[i] = lis[j] + 1; } } } }

01234567

위의 그림과 같은 순서로 lis배열에 값이 채워지게 된다.

최종적으로 최장 증가 부분 수열을 찾기 위해선, lis배열의 값들 중 가장 큰 값을 찾아주면 된다.

이 LIS를 사용하는 문제 중 하나인 

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

TEST CASE를 A전봇대 순서를 기준으로 정렬 후에 나열해 본다면, 8 2 9 1 4 6 7 10 이란 수열이 나오게 된다.

이 중 증가 수열의 집합에 속하지 않는 것을 제외시켜주면 답이 나오게 된다.

#include <iostream> #include <algorithm> using namespace std; int n; int cnt = 0; pair <int, int> s[101]; int lis[101]; void LIS() { lis[0] = 1; for (int i = 1; i <= n; i++) { lis[i] = 1; for (int j = 1; j < i; ++j) { if (s[j].second < s[i].second && lis[j] + 1 > lis[i]) { lis[i] = lis[j] + 1; } } } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> s[i].first >> s[i].second; } sort(s, s + n+1); LIS(); int maxnum=0; for (int i = 0; i <= n; i++) { maxnum = max(lis[i], maxnum); } cout << n-maxnum; }