이 두 문제를 풀었다면 쉽게 풀 수 있다.
각각의 부분 수열 cache를 구한 다음,
이를 각각 더하는 과정에서 최대 값이 정답이다.
한쪽만 풀고 도전했다면 충분히 풀 수도 있지만,
한 방향에서만 해결하려고 하면 반드시 함정에 걸리게 된다.
처음에 다음 값하고 비교해서, 값이 작아지는 부분부터 계산하는 식으로 접근했지만,
이 값이 작아지는 부분을 건너 뛰고 다음 작아지는 부분을 비교해야 하는 부분에서 난관을 겪었다.
결론은 반대로도 생각했으면 풀었을 문제였다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, i, j, ans1 = 1, ans2 = 0, result = 0;
vector <int> v(1024);
int upCache[1024] = { 1, };
int downCache[1024] = { 1, };
cin >> n;
for (i = 0; i < n; i++)
cin >> v[i];
for (i = 1; i < n; i++)
{
upCache[i] = 1;
for (j = 0; j < i; j++)
{
if (v[i] > v[j])
upCache[i] = max(upCache[i], upCache[j] + 1);
ans1 = max(ans1, upCache[i]);
}
}
for (i = n - 1; i >= 0; i--)
{
downCache[i] = 1;
for (j = n - 1; j >= i; j--)
{
if (v[i] > v[j])
downCache[i] = max(downCache[i], downCache[j] + 1);
ans2 = max(ans2, downCache[i]);
}
}
for (i = 0; i < n; i++)
result = max(result, downCache[i] + upCache[i]);
cout << result - 1;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
백준 [11657] 타임머신 (0) | 2021.02.18 |
---|---|
백준 [1707] 이분 그래프 (bfs) (0) | 2021.02.13 |
백준 [9251] LCS (0) | 2021.01.22 |
백준 [12865] 평범한 배낭 (0) | 2021.01.22 |
백준 [2580] 스도쿠 (0) | 2021.01.21 |