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

 

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

 

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

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

---

 

해결전략

 

가장 긴 증가하는 부분 수열   종류의 문제

 

 

---

 

코드

 

#include <iostream>
#include <vector>
using namespace std;

int n; // 수열의 길이
vector<int> v, dpF, dpB; // 입력 받을 수열, 앞에서부터의 가장 긴 증가하는 부분 수열, 뒤에서부터의 가장 긴 감소하는 부분 수열

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n;
	v.resize(n);
	dpF.resize(n, 1);	dpB.resize(n, 1); // 초기값을 1로 설정. 아래 내용 참고.
	for(int i=0; i<n; i++){
		cin >> v[i];
	}

	dpF[0] = 1;
	dpB[n-1] = 1;

	// 앞에서부터의 가장 긴 증가하는 부분 수열을 찾는 과정
	for (int i = 1; i < n; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (v[j] < v[i] && dpF[i] < dpF[j] + 1) {
				dpF[i] = dpF[j] + 1; // 이전 값들 중 현재 값보다 작은 값들 중 가장 큰 dpF 값에 1을 더한 값을 dpF[i]에 저장
			}
		}
	}

	// 뒤에서부터의 가장 긴 감소하는 부분 수열을 찾는 과정
	for (int i = n - 2; i >= 0; i--)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (v[i] > v[j] && dpB[i] < dpB[j] + 1) {
				dpB[i] = dpB[j] + 1; // 이후 값들 중 현재 값보다 작은 값들 중 가장 큰 dpB 값에 1을 더한 값을 dpB[i]에 저장
			}
		}
	}

	int answer = 0;
	// 가장 긴 바이토닉 부분 수열의 길이를 찾는 과정
	for (int i = 0; i < n; i++) 
	{
		if (answer < dpF[i] + dpB[i] - 1) 
			answer = dpF[i] + dpB[i] - 1; // dpF와 dpB를 합한 값 중 가장 큰 값을 answer에 저장. 이 때, i 위치의 값이 중복으로 더해지므로 1을 뺀다.
	}

	cout << answer;

	return 0;
}

 

 

dpF.resize(n, 1); dpB.resize(n, 1); 초기값을 0이 아닌 1로 설정하는 이유는?

 

dpF와 dpB는 각각 앞에서부터와 뒤에서부터의 가장 긴 부분 수열의 길이를 저장하는 배열이다. 이 때, 각 위치의 수자체도 부분 수열을 이루는 요소이기 때문에, 초기값을 1로 설정한다.

즉, dpF[i]의 값이 1이라는 것은 자기 자신만으로 이루어진 부분 수열이 있다는 것을 의미하며, dpB[i]의 값이 1이라는 것 또한 자기 자신만으로 이루어진 부분 수열이 있다는 것을 의미한다.

따라서, dpF와 dpB의 초기값을 1로 설정하는 이유는 각 위치의 수 자체를 부분 수열의 한 부분으로 간주하기 때문이다. 이렇게 함으로써, 각 위치에서의 가장 긴 증가 혹은 감소 부분 수열을 찾을 때, 자기 자신을 포함한 부분 수열을 고려할 수 있다.

 

 

 

---

 

유사 문제

 

2023.07.14 - [⭐ 코딩테스트/백준] - [백준 11053번 C/C++] 가장 긴 증가하는 부분 수열

 

2023.08.29 - [⭐ 코딩테스트/백준] - [백준 12015번 C/C++] 가장 긴 증가하는 부분 수열 2

 

 

---