백준 11054 c++ "가장 긴 바이토닉 부분 수열" -PlusUltraCode-

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

 

[필자 사고]

동적 프로그래밍 문제이다.

언뜻 봤을 때는 LIS문제 같아 보이지만

LIS문제를 응용한 문제이다.

dp배열을 2개 만들어 시작부분과 끝부분에서 각 시작하여

각 인덱스마다 2개의 배열을 더한 값-1 이 가장 큰값을 출력해야 된다.

 

필자는 해당 LIS를 구할 때 초기값을 1 로 설정을 안해서 출력값이 계속 1보다 작은 문제가 발생했었다.

이 부분 주의해야 겠다.

 

개인적으로 해당 문제에서 LIS지식을 2개를 이용하여 처음 부분과 끝부분으로 알고리즘 적용한게 인상적이였다.

[코드 해설]

1. 입력 처리 (Input 함수)
   Input() 함수는 배열의 크기 N을 입력받고, 이를 기반으로 배열 arr, dp, rDp를 초기화한다.

• arr 배열은 입력받은 수열을 저장하며, dp와 rDp는 각각 정방향과 역방향에서의 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 길이를 저장하는 벡터이다.
• arr2는 arr을 뒤집은 배열로, reverse(arr2.begin()+1, arr2.end())을 사용하여 첫 번째 원소를 제외한 나머지를 뒤집는다. 이를 통해 역방향에서의 LIS를 계산할 수 있도록 한다.

1. 최장 바이토닉 수열 계산 (Game_Start 함수)
   Game_Start() 함수는 dp와 rDp를 활용하여 최장 바이토닉 부분 수열(Longest Bitonic Subsequence)을 계산한다.

• dp[i]는 i번째 원소를 끝으로 하는 최장 증가 부분 수열의 길이를 나타낸다.
• rDp[i]는 arr2를 이용하여 i번째 원소를 시작으로 하는 최장 증가 부분 수열의 길이를 계산한 후, 다시 뒤집어 원래 배열의 역방향 LIS 값을 저장한다.
• 두 개의 LIS 정보를 조합하여 최장 바이토닉 부분 수열의 길이를 구한다.

이 과정에서 이중 루프를 사용하여 dp와 rDp를 채운다.

• dp[i] = max(dp[i], dp[k] + 1), rDp[i] = max(rDp[i], rDp[k] + 1)을 이용하여 LIS 값을 갱신한다.
• reverse(rDp.begin() + 1, rDp.end())을 사용하여 rDp를 원래 순서로 되돌린다.

최종적으로 resultCount를 이용하여 dp[i] + rDp[i]의 최댓값을 구하고, 한 번 중복된 원소를 제거하기 위해 -1을 한 결과를 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

vector<int> dp;
vector<int> rDp;
vector<int> arr;
vector<int> arr2;
int N;
void Input() {
	cin >> N;
	arr.resize(N + 1);
	dp.resize(N + 1,1);
	rDp.resize(N + 1,1);
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	arr2 = arr;
	reverse(arr2.begin()+1, arr2.end());
}

void Game_Start() {
	
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k < i; k++) {
			if (arr[i] > arr[k]) {
				dp[i] = max(dp[i], dp[k] + 1);
			}
			if (arr2[i] > arr2[k]) {
				rDp[i] = max(rDp[i], rDp[k] + 1);
			}
		}
	}
	
	reverse(rDp.begin() + 1, rDp.end());

	int resultCount = -1;
	for (int i = 1; i <= N; i++) {
		
		resultCount = max(resultCount, rDp[i] + dp[i]);
	}

	cout << resultCount-1;
}

int main(void) {
	Input();
	Game_Start();
}