[백준 알고리즘] 7570 c++ 줄 세우기

 

전체 어린이 수 - 가장 큰 1씩 증가하는 부분 수열 = 정답

어린이를 초기 위치에서 맨 앞이나 맨 뒤로만 이동시킬 수 있음. 

 

---

 

1. n 명의 어린이들 위치를 정렬시키는 데에는 최대 n 번이 걸림

2. 최대 n번 옮기되, 옮기지 않아도 되는 수가 존재 -> 가장 긴 1씩 증가하는 부분수열을 제외한 수만큼 옮기는 것이 최소화하는 방법

3. 단, n 제곱의 LIS 방법으로 부분수열을 구하게 된다면 시간초과가 날 것 (n의 수  ==  1,000,000)

4. 부분수열을 구하는 점화식이 중요4

 

---

점화식 : DP[입력된 아이의 번호] = DP[입력된 아이의 번호 - 1] + 1

 

 

 

순방향 정렬이기 때문에, i = 1 노드부터 올라가며 진행하면 된다.

 

#include <iostream>
#include <algorithm>

int list[1000001] = {};
int dp[1000001] = {};

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n;
	std::cin >> n;

	for (int i{ 1 }; i <= n; i++) std::cin >> list[i];

	int ans = 0;
	for (int i{ 1 }; i <= n; i++) {
		dp[list[i]] = dp[list[i] - 1] + 1;
		ans = std::max(dp[list[i]], ans);
	}

	std::cout << n - ans << "\n";
}