[BOJ] 11054 가장 긴 바이토닉 부분 수열 - LIS

2022.01.16 - [프로그래밍/알고리즘] - [BOJ 11053] 가장 긴 증가하는 부분수열 - LIS
11053과 거의 흡사한 문제이다.
차이가 있다면 바이토닉 이라는 조건이 추가 된 것이다.
아래의 그림을 보도록 하자.

원소를 추가해가며 LIS를 만드는 것은 이전 문제와 같으나,
더 큰 원소가 들어왔을때에 바이토닉 배열을 갱신해준다.
N번째 원소보다 작은 것들로 이루어진 LIS의 배열의 크기를 LISLessThan[N] 이라고 하자.
LIS를 만들며 이 배열을 갱신할 것이다.
1 2 3 4 5 6 에 7이 들어오면, LIS의 길이는 7이 되고, 이때에 LISLessThan[7] 은 7이 된다.
위 그림에서 빨간색으로 표시된 경우를 보도록 하자.
1 2 3 4 5 6 에 3이 들어오면, LIS는 길이는 그대로 6이고, 이때에 LISLessThan[7] 은 3이 된다.
왜 ? 들어온 원소 3보다 작은 원소는 몇개인지 찾아본다.
1과 2다. 들어온 원소 자기자신인 3을 포함해서 LISLessThan[7]은 3이 된다.
같은 방식으로 LIS를 구하는데, 뒤쪽의 원소부터 추가해가며 LIS를 만들어가면,
N에서 1로 진행하며 감소하는 수열을 만들어갈 수 있다.
이 값 또한 계속해서 갱신해준다.
코드는 다음과 같다.
마지막의 -3의 경우는, vector.back을 쓰기위해서 -1을 미리 넣어둔 것이다.
그래서 각각 -1씩 두번 -2,
또한 각 배열 LISLessThan 과 RLISBiggerThan은 자기자신을 포함한 값이 들어있다.
두번 적용되면 안되므로, -1을 해준다.
#include <iostream> #include <algorithm> #include <vector> int Cost[1001] = { 0 , }; int LISLessThan[1001] = { 1 , }; int RLISBiggerThan[1001] = { 1 , }; int main() { std::cin.tie(0); std::cout.tie(0); std::cin.sync_with_stdio(false); std::cout.sync_with_stdio(false); int N; int MaxIdx = 0; std::cin >> N; std::vector<int> LIS; std::vector<int> RLIS; LIS.push_back(-1); RLIS.push_back(-1); LISLessThan[0] = 1; RLISBiggerThan[N] = 1; for (int i = 1; i <= N; ++i) { std::cin >> Cost[i]; LISLessThan[i] = 1; if (Cost[i] > LIS.back()) { LIS.push_back(Cost[i]); LISLessThan[i] = LIS.size(); } else { LISLessThan[i] = LISLessThan[i - 1]; for (int k = 0; k < LIS.size(); ++k) if (LIS[k] >= Cost[i]) { LISLessThan[0] = k + 1; LIS[k] = Cost[i]; break; } } } for (int i = N; i >= 1; --i) { if (Cost[i] > RLIS.back()) { RLIS.push_back(Cost[i]); RLISBiggerThan[i] = RLIS.size(); } else { for (int k = 0; k < RLIS.size(); ++k) if (RLIS[k] >= Cost[i]) { RLISBiggerThan[i] = k + 1; RLIS[k] = Cost[i]; break; } } } int Res = 0; for (int i = 1; i <= N; ++i) Res = std::max(Res, LISLessThan[i] + RLISBiggerThan[i]); std::cout << Res - 3; return 0; }
'알고리즘' 카테고리의 다른 글
[BOJ] 9461 파도반 수열 - 동적 계획법 (0) | 2022.01.17 |
---|---|
[BOJ] 2565 전깃줄 - LIS (0) | 2022.01.17 |
[BOJ] 11053 가장 긴 증가하는 부분수열 - LIS (0) | 2022.01.16 |
[BOJ] 2156 포도주 시식 - 동적 계획법 (0) | 2022.01.14 |
[BOJ] 10844 쉬운 계단수 - 동적 계획법 (0) | 2022.01.13 |
댓글
이 글 공유하기
다른 글
-
[BOJ] 9461 파도반 수열 - 동적 계획법
[BOJ] 9461 파도반 수열 - 동적 계획법
2022.01.17 -
[BOJ] 2565 전깃줄 - LIS
[BOJ] 2565 전깃줄 - LIS
2022.01.17 -
[BOJ] 11053 가장 긴 증가하는 부분수열 - LIS
[BOJ] 11053 가장 긴 증가하는 부분수열 - LIS
2022.01.16 -
[BOJ] 2156 포도주 시식 - 동적 계획법
[BOJ] 2156 포도주 시식 - 동적 계획법
2022.01.14
댓글을 사용할 수 없습니다.