백준 BOJ 2631 - 줄세우기

백준랜덤디펜스 도중에 만난 문제

예전에도 지문을 한번 읽었던거같은데

바로 아이디어 떠올릴수있는거보면

실력이 늘긴 늘은거같아서 흐뭇하다

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

2631번: 줄세우기

lis임을 관찰해내기 어려워서 골드4라고 하는데,

개인적으로는 좀 빠르게 찾아낼 수 있었다.

 

처음에는 머지소트를 사용해서 교차횟수를 세는 문제인가? 라는 생각을 하고 시작했다.

근데 이 문제는 버블정렬처럼 인접한 두 원소를 swap 하는게 아니고,

저 멀리 떨어져있는 것들을 이동할수 있었기에 일단 머지소트는 아니라는걸 알 수 있었다.

 

이동되는 값들을 보면서 생각하고 있다가,

값을 움직일 때마다 정렬에 "한 걸음" 가까워져야지만

최소의 횟수로 정렬을 할 수 있다는 생각이 들었다.

 

나중에 정렬에 써먹을 수 있는 수들은 건드리지 말고,

정렬을 방해하는 값들만 쏙쏙 뽑아다가 옮기면 정렬이 되겠다는 생각에 도달한다면

LIS를 통해서 "정렬에 써먹을 수 있는 수" 의 갯수를 구할 수 있다.

 

LIS가 최장 증가 부분 수열, 즉 이미 정렬되어있는 부분수열의 최대 길이이기 때문에

이 이미 정렬되어있는 부분수열들을 건드리지 말아야 최적해를 구할 수 있다.

 

LIS에 포함되지 못한 원소들을 필요한 위치에 배치해야 정렬을 끝마칠 수 있기 때문에,

문제에서 요구하는 옮겨지는 아이의 최소 수는 전체 수열의 길이에서 LIS의 길이를 빼면 된다.

 

N의 범위가 200으로 굉장히 작은 편이기에

LIS를 O(N^2) 로 구해도 AC를 받을 수 있다.

나는 그냥 몸에 익어서 O(NlogN) 으로 짰다.

 

배열처럼 수가 일직선으로 들어와서 이런 생각하기가 쉽지 않은거같긴 한데

인덱스를 기반으로 수를 swap 한다는 느낌보다는

그냥 수를 연결리스트 다루듯이 뽑아서 옮길 수 있다 라고 생각한다면

좀 더 답에 가까워지기 쉬운 거 같다.

 

#include <bits/stdc++.h>
using namespace std;

int arr[234] = {0};
vector<int> v;

int main(){
	int N;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> arr[i];
		if(!i) v.push_back(arr[i]);
		else{
			if(v.back() < arr[i]){
				v.push_back(arr[i]);
			}
			else{
				auto it = lower_bound(v.begin(), v.end(), arr[i]);
				*it = arr[i];
			}
		}
	}
	
	cout << N-v.size();
	
	return 0;
}