[BAE/<JOON> 문제풀이] 7570. 줄 세우기

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

7570번: 줄 세우기

핵심::
DP문제

풀이::
일반적인 nlogn LIS 전깃줄 문제 같아 보인다.

하지만 학생을 항상 맨 뒤나 맨 앞으로만 뺄 수 있기 때문에 일반적인 LIS문제로 풀이할 경우 다음과 같은 반례가 생긴다.

1 2 3 5 6 4 

위의 예제의 경우 LIS를 구하면 1 2 3 5 6 으로 총 5의 길이를 가지기 때문에 정답이 1로 나오지만

4번 어린이를 3과 5 사이에 삽입하는 것은 불가능하다. 

LIS를 구하는 이유가 바꿀 필요가 없는 어린이 수를 구하기 위함이지만 이 문제에서는 1~N까지의 어린이들이 차례대로 주어지므로

구한 LIS가 연속하지 않을 경우 결국 구한 LIS 사이에 새로운 어린이를 삽입해야하고 구한 LIS가 의미 없어진다.

LIS를 구하되 연속하는 LIS를 구해야 한다.

어린이들의 숫자가 각각 1번씩만 등장한다는 사실을 이용해 O(n)의 풀이를 떠올릴 수 있다.

arr[N] = N번 어린이 번호

idx[arr[N]] = N번 어린이의 위치

DP[N] = N번까지 연속하는 LIS길이 총합

if idx[arr[N] - 1] < idx[arr[N]] && arr[N] != 1 //번호가 1이라면 절대 다른 배열 뒤에 올 수 없다.
dp[N] = dp[idx[arr[N] - 1]] + 1

만약 현재 번호를 가진 어린이 위치보다 현재 번호 - 1의 번호를 가진 어린이의 위치가 더 앞에 있다면

현재 번호로 뒤에 있는 LIS 배열 길이를 연장할 수 있다.

의견::
주어지는 입력의 크기를 보면 많은 힌트를 얻을 수 있는 것 같다. 아무 생각 없이 nlogn LIS 풀이를 적용하려 했지만
10^6의 입력크기는 nlogn의 입력으로도 1초 안에 처리하기 힘든 입력 양이다.

코드::

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

int main()
{
	int n;
	cin >> n; vector<int> arr(n + 1);
	vector<int> dp(n + 1, 1);	
	vector<int> idx(n + 1);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &arr[i]);
		idx[arr[i]] = i;
	}	

	int mx = 1;
	for (int i = 2; i <= n; i++) {
		if (idx[arr[i] - 1] < idx[arr[i]] && arr[i] != 1) {
			dp[i] = dp[idx[arr[i] - 1]] + 1;
			mx = dp[i] > mx ? dp[i] : mx;
		}
	}

	cout << n - mx;

	return 0;
}