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

분석 및 후기

일단 너무 아쉬웠다. 1시간안에 못풀기는 했는데

딱 1시간쯤에 생각나던 부분에 부분증가 수열을 거구로 돌리면 어떻게 될까? 였다.

그래서 아래의 코드는 이해하였기 때문에

for (int i = 1; i <= n; ++i)
{
	for (int j = 1; j < i; ++j)
		if (arr[i] > arr[j])
			cache1[i] = max(cache1[i], cache1[j] + 1);
}

위의 그림처럼 거꾸로 돌린다면 어떻게되는지 그려가며 확인했다.

그래서 아~ 이거 캐시를 하나만 쓰면 안되겠고
캐시를 두개를 써야겠다.
뭐 LeftCache, RightCache이런식으로

이까지는 잘 왓던거 같았는데

아래와 같이 짜기는했다.

int main()
{	
	int n;
	cin >> n;
	
	for (int i = 1; i < n + 1; ++i) cin >> arr[i];

	for (int i = 1; i <= n; ++i) cache1[i] = 1;

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j < i; ++j)
			if (arr[i] > arr[j])
				cache1[i] = max(cache1[i], cache1[j] + 1);
	}

	for (int i = n; i > 0; --i)
	{
		for (int j = n; j > i; --j)
			if (arr[i] > arr[j])
				cache2[i] = max(cache2[i], cache2[j] + 1);
	}
	
	return 0;
}

근데 여기서 뇌정지도 오고 힘들어서 어떻게 출력해야 맞는것인지 몰라서 ㅈㅈ 치고

해설을 보고 아하~ 하면서 이해를 하긴함...

조금더 문제를 많이 풀어봐야할듯..

cpp코드

#include <iostream>
using namespace std;

#define MAX 1001
#define endl "\n"

int cache1[MAX];
int cache2[MAX];
int arr[MAX];

int main()
{	
	int n;
	cin >> n;
	
	for (int i = 1; i < n + 1; ++i) cin >> arr[i];

	for (int i = 1; i <= n; ++i) cache1[i] = 1;

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j < i; ++j)
			if (arr[i] > arr[j])
				cache1[i] = max(cache1[i], cache1[j] + 1);
	}

	for (int i = n; i > 0; --i)
	{
		for (int j = n; j > i; --j)
			if (arr[i] > arr[j])
				cache2[i] = max(cache2[i], cache2[j] + 1);
	}
	
	int answer = 0;
	for (int i = 1; i < n + 1; ++i)
		answer = max(answer, cache1[i] + cache2[i]);
	
	cout << answer;

	return 0;
}