[백준] 7570 - 줄 세우기

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

7570번: 줄 세우기

 

해결 방법이 떠오르지 않아 다른 블로그를 참고하였다.

 

핵심은 LIS(Longest Increasing Subsequence)였다. 주어지는 수열의 LIS를 찾고, 총길이 - LIS의 길이가 답이다.

하지만 보통의 LIS가 아니고 연속적인 숫자를 가진 LIS를 찾아야 한다.

 

LIS를 찾는 과정은 index 배열을 이용해 현재 수의 이전 수가 앞에 나온 적이 있는가 없는가로 판단해 구하였다.

 

#include <iostream>
using namespace std;

int idx[1000001];
int a[1000001];
int dp[1000001];
int n;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		idx[a[i]] = i;
	}
	int ans = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (idx[i] > idx[i - 1]) {
			dp[i] = dp[i - 1] + 1;
		}
		else dp[i] = 1;
		ans = max(ans, dp[i]);
	}
	cout << n - ans;
}

 

Reference

https://mygumi.tistory.com/276