[백준/BOJ] 백준 7570번 : 줄 세우기

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

7570번: 줄 세우기

 

1씩 증가하는 가장 긴 증가하는 부분 수열의 길이를 구해, 해당 부분 수열이 아닌 다른 숫자들을 앞이나 뒤로 보내는 접근으로 문제를 해결했다.

 

이때, cache[number] = number 숫자 위치에서 끝나는 1씩 증가하는 부분수열의 길이를 저장하는 다이나믹 프로그래밍을 이용했다.

 

코드

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

//가장 긴 증가하는 부분 수열(LIS)을 다이나믹 프로그래밍을 통해 찾아서 문제를 해결했다
//그런데 이때, 가장 긴 증가하는 부분 수열(LIS)을 구할때, 정확히 1씩 증가하는 부분 수열을 구해야 한다.

int n;
int cache[1000005];

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int num;
		cin >> num;

		cache[num] = cache[num - 1] + 1; //num 숫자보다 num-1 숫자가 앞에서 먼저 등장했다면, 이어져서 증가하는 부분 수열이 생긴다 
	}

	int max_len = 0; //가장 긴 증가하는 부분 수열의 길이
	for (int i = 1; i <= n; i++) {
		max_len = max(max_len, cache[i]);
	}
	int result = n - max_len; //전체 수 - 가장 긴 증가하는 부분 수열의 길이를 통해 이동하는 최소 수를 구한다

	cout << result;

	return 0;
}