백준 알고리즘 11054번: 가장 긴 바이토닉 부분 수열 [C++]

문제 출처: www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

1. 코드

#include <iostream>

using namespace std;

int main(void)
{
	int n, a[1000], left[1000], right[1000];	//n = 수열 a의 크기, a = 입력된 수열, left = 왼쪽부터 시작하는 LIS, right = 오른쪽부터 시작하는 LIS
	int result = 0;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> a[i];

	for (int i = 0; i < n; i++)			//왼쪽에서 LIS 알고리즘 적용
	{
		left[i] = 1;
		for (int j = 0; j <= i; j++)
			if (a[j] < a[i] && left[i] < left[j] + 1)
				left[i]++;
	}

	for (int i = n - 1; i >= 0; i--)	//오른쪽부터 LIS 알고리즘 적용
	{
		right[i] = 1;
		for (int j = n - 1; j >= i; j--)
			if (a[j] < a[i] && right[i] < right[j] + 1)
				right[i]++;
	}
	
	for (int i = 0; i < n; i++)			//왼쪽과 오른쪽의 합이 제일 큰 값 찾기
		if (result < left[i] + right[i])
			result = left[i] + right[i];
	cout << result - 1;					//중복되는 중복값 제거로 인한 -1
	return 0;
}

(실행)

2. 풀이

A의 배열이 위와 같을 때 왼쪽부터 시작하는 LIS와 오른쪽부터 시작하는 LIS의 길이를 합한 결과의 -1을 하면 원하는 해답이 나온다. -1을 하는 이유는 중간에 있는 값이 중복이 되기 때문에 1개를 제거한 것인데 자세한 과정은 천천히 설명하겠다.

왼쪽부터 시작하는 LIS

먼저 위 그림은 왼쪽부터 시작하는 LIS이다. 보면 가장 긴 경우의 배열은 1, 3이다.

오른쪽부터 시작하는 LIS

그리고 위 그림은 오른쪽부터 시작하게되는데 가장 긴 경우는 1, 2, 3이다. 그렇다면 왼쪽과 오른쪽으로 진행된 left와 right를 합치게 된다면 1, 2, 3, 3, 1이다. 3이라는 중간값이 겹치기 때문에 마지막에 -1을 해주어 3이 제거된 길이를 구해준다. 그러면 최종적으로 1, 2, 3, 1이 되고 바이토닉 수열로 구성이 되며 길이는 4가 된다.

3. 느낀 점

처음에 동적 계획법은 규칙만 찾으면 간단할 줄 알았다. 하지만 이제는 규칙 조차 찾는게 어렵다는 느낌이 상당히 강하고 규칙을 찾더라도 그 규칙에 맞는 구현 능력이 부족하여 구현을 잘 못하여 다른 사람의 코드를 계속해서 보게되는 것 같다. 그래도 풀이 방법에 대해 정확히 알게 되고 꾸준하게 복습을 한다면 점점 좋아질거라고 믿고 있다.