[11548번] 민균이의 계략

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

이 문제는 제시한 카드의 수열이 순증가가 아니면 민균이에게 바보라고 놀림받게 된다. 라는 내용에서 LIS를 캐치 할 수 있다.

그리고 LIS 알고리즘의 가장 기본이 되는 문제이다.

LIS 개념에 대한 내용은 위의 링크를 참조하면 되고

그 외 다양한 문제는 http://www.crocus.co.kr/search/LIS 를 참조해보자.

(사실 위의 두 링크에서 LIS를 계속해서 설명해왔기에 이 문제에서는 설명할 것이 없어보인다.)

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

#include <iostream> #include <cstdio>   using namespace std;   int arr[1002]; int lis[1002];   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;       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];         }           pArr++;     }       printf("%d", pLis + 1);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus