[1965번] 상자넣기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

상자넣기 문제는 LIS 알고리즘으로 해결 할 수 있다.

1 6 2 5 7 3 5 6일 경우

정답은 1 2 3 5 6인 5개가 정답일 것이다.

이 말은 즉슨, 가장 긴 증가하는 부분 수열을 찾아내라는 의미와 같은 것이고 결국 이 알고리즘이 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 56 57 58 59 60 61 62

#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 (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;       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];         }         /*             //lis 검증 코드             for (int i = 0; i < n; i++)                 printf("%d ", lis[i]);             printf("\n");         */     }     printf("%d", pLis + 1);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus