[C/C++] 백준 7570번 - 줄 세우기 (DP, LIS)

 

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;

int N;
int dp[1000001];
int x, ans;

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

	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> x;
		dp[x] = dp[x - 1] + 1;
		ans = max(ans, dp[x]);
	}
	cout << N - ans;
}

 

풀이 방법

 

+1씩 증가하는 LIS(최장증가수열)을 찾은 뒤 해당 수열을 고정하고 나머지 어린이들을 이동시키면 됩니다.

 

 

 

www.acmicpc.net/problem/7570

7570번: 줄 세우기