[그리디 #21] BOJ 7570 - 줄 세우기

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

 

7570번: 줄 세우기

 

1차 시도

처음에 이걸 그리디로 해결하기 위해서 다음과 같이 생각했다.

 

1. 앞으로 옮겼을 때, 뒤쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야한다.

2. 뒤로 옮겼을 때, 앞쪽에 자신보다 큰 수들이 많이 위치하는 것을 골라야 한다.

 

그러나 이것은 금방 틀리다는 것을 알 수 있다.

가령 1,2번이 맞다고 하더라도 순서대로 이어져있지 않으면 문제가 된다.

 

따라서, 순서를 집중해서 공략하는게 좋겠다고 생각했다.

 

순서대로인 부분수열 중 가장 긴 것을 골라야, 부분수열이 아닌 나머지 수가 가장 최소가 되므로

가장 긴 부분수열 중 순서대로 인 것을 찾아야 함을 알게 되었다.

 

이를 구현하기 위해서 DP를 이용하였다.

 

예전에 풀었던 가장 긴 증가하는 부분수열을 이용하여 구현하였는데 틀렸다.

https://meteorfish.blog/65

[👊DP뿌시기 #7] (BOJ 11053) 가장 긴 증가하는 부분 수열

 

O(N^2)로 풀게되면 시간초과가 나게된다...

 

이를 어떻게 하면 시간복잡도를 줄일 수 있을까 고민했다.

 

 

2차 시도

질문 게시판을 참고하였다..

 

굳이 i보다 이전들을 파해치며, 가장 큰 dp를 구할 필요가 없다.

 

dp를 0으로 초기화 한 후, dp[i-1]이 0이 아니면 dp[i] = dp[i-1] + 1을 하면되고,

dp[i-1]이 0이면, dp[i] 를 1로 두면된다.

 

따라서, 위 알고리즘을 이용하여 O(N)에 해결할 수 있다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define MAX 1000001

int n;
int arr[MAX];
int res = -1;


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

	cin >> n;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		// 이전이 없으면 1
		if (arr[tmp - 1] == 0) {
			arr[tmp] = 1;
		}
		else {
			arr[tmp] = arr[tmp - 1] + 1;
			res = max(res, arr[tmp]);
		}
	}
	if (n != 1)
		cout << n - res;
	else
		cout << 0;
}