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

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

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net)

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

괜히 고민을 많이 했는데 결국에는 가장 직관적으로 문제를 풀었다. 계산을 대충 해도 두 번의 이중 for문을 돌렸을 때 \( 1000 \times 1000 \times 2 = 2 \times 10^{6} = 2000000 \)의 연산이 필요하다. 즉, 1억 번에 한참 못 미치는 연산을 수행해도 가능하다.

 

예전에 파이썬으로 풀었던 문제다. 아래에 글 링크를 첨부했는데, 지금 보니까 이때 풀었던 방식과 동일하다. 아직 풀이를 쓰기 전인데.. 아래의 설명이 부족하다면 이 글을 통해 보면 좀 더 이해할 수 있지 않을까.. 생각한다.

[백준알고리즘] 11054번: 가장 긴 바이토닉 부분 수열 -Python (tistory.com)

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

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

 

---

 

바이토닉 수열에 대해서 위키나 다른 글을 참고하려 했는데, 바이토닉 정렬만 나오고 잘 나오지 않았다. 바이토닉 정렬과 관련된 수열인 건가? 

아무튼 문제에서 바이토닉 수열은 증가하다가 감소하는 형태의 수열이라 정의하고 있다. 이때, 그냥 증가하는 수열과 감소하는 수열도 포함된다.

 

이때 중요한 것은 문제에서 요구하는 것이 바이토닉 수열이 아니다. 생성 가능한 가장 긴 바이토닉 수열의 길이일 뿐이다.

 

 

증가하다가 감소하는 수열을 구하기 위해서 다음 두 가지를 구해주었다.

1. 주어진 수열에 대해서 각 원소까지의 증가하는 순열의 최대 길이
2. 뒤집한 수열에 대해서 각 원소까지의 증가하는 수열의 최대 길이

 

위 두 가지를 구해줌으로써 각 인덱스까지의 증가하는 순열의 최대 길이를 구할 수 있고, 역으로 뒤집힌 수열의 각 인덱스까지의 증가하는 수열의 최대 길이를 구해줄 수 있는 것이다.

 

따라서 이 두 가지 경우를 더한 뒤 1을 빼주면, 각 원소를 포함했을 때의 가장 긴 바이토닉 수열 (증가하다가 감소하는 수열)을 만들 수 있게 된다.

 

음.. 설명이 간단한 것 같지만, 정말 저게 전부다. 아래의 코드를 보면 좀 더 쉽게 이해가 될 수 있다. 바이토닉 수열의 길이를 구하는 함수가 getLengthLongestBitonic이다. 여기서 두 개의 이중 for문이 존재하는데, 첫 번째가 순차적으로 구했을 때 각 인덱스에서 구할 수 있는 가장 긴 증가하는 수열의 길이를 구한다. 두 번째가 역으로 뒤집힌 sequence에 대해서 각 인덱스에서 구할 수 있는 가장 긴 증가하는 수열의 길이를 구한다. 이 두 수열을 합하고 1을 뺀 값을 return 하도록 가장 긴 바이토닉 수열의 길이를 구했다.

#include <iostream>
#include <vector>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL); 
	std::cout.tie(NULL); 
	
	solve();
}

int getLengthLongestBitonic(const std::vector<int>& sequence)
{
	int sequenceLength = sequence.size();
	std::vector<int> direct(sequenceLength, 0);
	std::vector<int> reverse(sequenceLength, 0);

	for (int i = 0; i < sequenceLength; i++)
	{
		int length = 1;

		for (int j = 0; j < i; j++)
		{
			if (sequence[i] <= sequence[j])
				continue;

			length = std::max(length, direct[j] + 1);
		}

		direct[i] = length;
	}

	for (int i = sequenceLength - 1; i >= 0; i--)
	{
		int length = 1;

		for (int j = sequenceLength - 1; j > i; j--)
		{
			if (sequence[i] <= sequence[j])
				continue;

			length = std::max(length, reverse[j] + 1);
		}

		reverse[i] = length;
	}

	int maxLength = 0;
	for (int i = 0; i < sequenceLength; i++)
		maxLength = std::max(maxLength, direct[i] + reverse[i] - 1);

	return maxLength;
}

void solve(void)
{
	int n;
	std::cin >> n;

	std::vector<int> sequence(n);
	for (int i = 0; i < n; i++)
		std::cin >> sequence[i];

	std::cout << getLengthLongestBitonic(sequence);
}