[1365번] 꼬인 전깃줄

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. LIS 알고리즘 :: http://www.crocus.co.kr/583

LIS로 해결할 수 있는 문제이다.

문제 예제처럼 2 3 4 1을 보자.

lis 배열에 들어오는 과정을 보면

2

2 3

2 3 4

1 3 4

이렇게 변한다.

1이 즉 4번째에 있어야 하는데 1번째로 왔다. 결국 3칸 움직였다는 의미는 3개의 선이 꼬였다는 것이다.(1과 2,3,4)

다른 예제를 보자

2 5 3 4 1이 있다고 생각하면

2

2 5

2 3 :: 3번째에 있어야 하는 것이 2번째로 왔다. 즉, 3과 5가 꼬여있다는 의미이다.

2 3 4

1 3 4 :: 4번째에 있어야 할 것이 1번째로 왔다. 즉, 3개의 선이 꼬였다는 의미이다.

(그림으로 그리면 총 4개의 선이 꼬여있지만, 그림을 순차적으로 그리면 이미 2->5선은 지워진 상태이라 생각할 수 있고

결국 3개의 선이 꼬여있는 것이다.)

소스 코드 : 

/*
 * Problem :: [1365번] 꼬인 전깃줄
 * Date :: 2017/03/17
 * link :: https://www.acmicpc.net/problem/1365
 *
 * http://www.crocus.co.kr
*/
 
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int arr[100001];
int lis[100001];
 
int _lower_bound(int start, int end, int target)
{
    int mid;
 
    while(start < end)
    {
        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 pLis = 0, pArr = 1, cnt = 0;
 
    lis[pLis] = arr[0];
 
    while(pArr < n)
    {
        if(lis[pLis] < arr[pArr])
            lis[++pLis] = arr[pArr];
 
        else
        {
            int ans = _lower_bound(0, pLis, arr[pArr]);
            lis[ans-1] = arr[pArr];
            cnt++;
        }
 
        pArr++;
    }
 
    printf("%d",cnt);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>