문제 출처 :
https://www.acmicpc.net/problem/11054
알고리즘 분석 :
문제 해결에 필요한 사항
1. LIS 알고리즘, 가장 긴 증가하는 부분 수열 :: http://www.crocus.co.kr/582
2. LDS 알고리즘, 가장 긴 감소하는 부분 수열 :: http://www.crocus.co.kr/669
3. LIS와 LDS의 조합
사실 LDS라는 말은 없지만 LIS와 반대로 동작하는 알고리즘을 설명하기 위해 LDS라고 지칭하겠다.
lis 알고리즘을 알고, lis를 역으로 이용할 수 있는 lds 알고리즘을 코딩하면 90%는 완료됐다.
만약 1 5 2 1 4 3 4 5 2 1 라는 배열이 있다면
바이토닉 수열을 구하기 위해서는
1 | 5 2 1 4 3 4 5 2 1
1 5 | 2 1 4 3 4 5 2 1
1 5 2 | 1 4 3 4 5 2 1
1 5 2 1 | 4 3 4 5 2 1
1 5 2 1 4 | 3 4 5 2 1
1 5 2 1 4 3 | 4 5 2 1
1 5 2 1 4 3 4 | 5 2 1
1 5 2 1 4 3 4 5 | 2 1
1 5 2 1 4 3 4 5 2 | 1
이렇게 구분선을 두어 왼쪽 lis 오른쪽 lds를 구하면 된다.
왼쪽 lis, 오른쪽 lds를 보자.
1 | 5 2 1 4 3 4 5 2 1 lis :: 1 lds :: 5 max :: 6
1 5 | 2 1 4 3 4 5 2 1 lis :: 2 lds :: 4 max :: 6
1 5 2 | 1 4 3 4 5 2 1 lis :: 2 lds :: 4 max :: 6
1 5 2 1 | 4 3 4 5 2 1 lis :: 2 lds :: 4 max :: 6
1 5 2 1 4 | 3 4 5 2 1 lis :: 3 lds :: 3 max :: 6
1 5 2 1 4 3 | 4 5 2 1 lis :: 3 lds :: 3 max :: 6
1 5 2 1 4 3 4 | 5 2 1 lis :: 4 lds :: 3 max :: 7
1 5 2 1 4 3 4 5 | 2 1 lis :: 5 lds :: 2 max :: 7
1 5 2 1 4 3 4 5 2 | 1 lis :: 5 lds :: 1 max :: 6
따라서 max (DP)는 7이 된다.
이렇게 | 구분자를 split라는 변수로 두어 lis와 lds의 구분 시작점을 나타내었다.
소스 코드 :
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 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #include <iostream> #include <cstdio> #include <memory.h> #define max(a, b)(a > b ? a : b) using namespace std; int arr[1001]; int lds[1001]; int lis[1001]; int DP; int lis_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 lds_lower_bound(int start, int end, int target) { int mid; while (start < end) { mid = (start + end) / 2; if (lds[mid] > target) start = mid + 1; else end = mid; } return end + 1; } int main() { int n; int pArr, pLis, pLds; int split = 1; scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &arr[i]); for (int i = 0; i < n - 1; i++) { memset(lis, 0, sizeof(lis)); memset(lds, 0, sizeof(lds)); pArr = 1, pLis = 0; lis[pLis] = arr[0]; while (pArr < split) { if (lis[pLis] < arr[pArr]) lis[++pLis] = arr[pArr]; else { int pos = lis_lower_bound(0, pLis, arr[pArr]); lis[pos - 1] = arr[pArr]; } pArr++; } pArr = split-1, pLds = 0; lds[pLds] = arr[split]; while (pArr < n) { if (lds[pLds] > arr[pArr]) lds[++pLds] = arr[pArr]; else { int pos = lds_lower_bound(0, pLds, arr[pArr]); lds[pos - 1] = arr[pArr]; } pArr++; } split++; DP = max(DP, pLis + pLds + 1); } printf("%d", DP); return 0; } // This source code Copyright belongs to Crocus // If you want to see more? click here >> | Crocus |
'Applied > 알고리즘 문제풀이' 카테고리의 다른 글
[1365번] 꼬인 전깃줄 (0) | 2017.03.17 |
---|---|
[3176번] 도로 네트워크 (0) | 2017.03.17 |
[11722번] 가장 긴 감소하는 부분 수열 (0) | 2017.03.17 |
[2243번] 사탕 상자 (2) | 2017.03.16 |
[3653번] 영화 수집 (0) | 2017.03.16 |