본문 바로가기

알고리즘/백준

백준 [11054] 가장 긴 바이토닉 부분 수열

이 두 문제를 풀었다면 쉽게 풀 수 있다.

www.acmicpc.net/problem/11722

 

11722번: 가장 긴 감소하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 

www.acmicpc.net

www.acmicpc.net/problem/11053

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

 

각각의 부분 수열 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