[1818번] 책정리

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LIS(Longest Increasing Subsequence) :: http://www.crocus.co.kr/583

이 문제는 LIS 알고리즘을 응용하여 해결 할 수 있다.

위의 그림을 통해 생각해보자.

2 1 4 5 3으로 책이 현재 정렬되어있다.

그렇다면 최소 횟수로 책을 정렬하기 위해서는

1. 1을 가장 앞으로 옮기고 -> 1 2 4 5 3

2. 3을 2다음 자리에 옮긴다 -> 1 2 3 4 5

이걸 다시 LIS 알고리즘으로 생각해보자.

2 1 4 5 3이 입력될 때 LIS 배열에는

2가 처음 들어오고 -> lower_bound에 의해 2가 1로 교체된다.

4는 1보다 크므로 1 4가 LIS 배열에 들어오고

4보다 5가 크므로 1 4 5가 LIS 배열에 들어온다.

3은 lower_bound에 의해 4가 3으로 교체되며 1 3 5가 형성된다.

여기서 알 수 있는 것은 책을 옮겨야 하는 대상은 lower_bound에 들어오게 된다.

즉, 1과 3이 교체되기 위해(자기 자리를 찾기 위해) 행동하는 것을 LIS 알고리즘으로 해결 할 수 있다.

결국 같은 말로

현재 책 - 가장 긴 부분 수열로 정렬되지 않은 나머지 책들 = 답 이라는 것이다.

1 2 4 5 3 

위의 붉은 색 책 하나가 제대로 정렬되어있지 않은 것을 의미

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int arr[200002];
int lis[200002];
 
int _lower_bound(int start, int end, int target)
{
    int mid;
    while (end - start > 0)
    {
        mid = (start + end) / 2;
 
        if (lis[mid] < target)
            start = mid + 1;
 
        else
            end = mid;
    }
 
    return end + 1;
}
 
int main()
{
    int n;
    
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    int pArr = 1;
    int pLis = 0;
    int cnt = 0;
    lis[0] = arr[0];
    
    for (pArr; pArr < n; pArr++)
    {
        if (lis[pLis] < arr[pArr])
            lis[++pLis] = arr[pArr];
 
        else
        {
            int ans = _lower_bound(0, pLis, arr[pArr]);
            lis[ans - 1] = arr[pArr];
            cnt++;
        }
        /*
            //lis 검증 코드
            for (int i = 0; i < n; i++)
                printf("%d ", lis[i]);
            printf("\n");
        */
    }
    printf("%d", cnt);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>