[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