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

1. 문제

 

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

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

 

2. 알고리즘 분류

• 다이나믹 프로그래밍

 

3. 소스 코드

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

int N, ans;
int arr[1000];
int dp_asc[1000];
int dp_dec[1000];
int dp_bitonic[1000];

void input() {
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> arr[i];
}

void solve() {
	// 오름차순 부분수열 크기 구하기(DP 이용)
	for (int i = 0; i < N; i++) {
		int max_val = 0;

		// 현재 위치에서 왼쪽으로 탐색
		// 현재 위치에 값보다 작은 경우, 해당 dp 테이블 값 중 최댓값 저장
		for (int j = 0; j < i; j++)
			if (arr[j] < arr[i])
				max_val = max(max_val, dp_asc[j]);

		dp_asc[i] = max_val + 1;
	}

	// 내림차순 부분수열 크기 구하기 (DP 이용)
	for (int i = N - 1; i >= 0; i--) {
		int max_val = 0;

		// 현재 위치에서 오른쪽으로 탐색
		// 현재 위치에 값보다 작은 경우, 해당 dp 테이블 값 중 최댓값 저장
		for (int j = N - 1; j > i; j--)
			if (arr[j] < arr[i])
				max_val = max(max_val, dp_dec[j]);

		dp_dec[i] = max_val + 1;
	}

	// 바이토닉 수열 = 해당 위치의 오름차순 부분수열 크기 + 해당 위치의 내림차순 부분수열 크기 - 1
	// 해당 위치(i 위치)가 중복되므로 1을 빼줌
	for (int i = 0; i < N; i++) {
		dp_bitonic[i] = dp_asc[i] + dp_dec[i] - 1;
		ans = max(ans, dp_bitonic[i]);	// 최댓값을 ans에 저장
	}
}

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

	input();
	solve();
	cout << ans;	// ans 출력

	return 0;
}

 

4.  순서도

 

5.  풀이 과정

예제 입력 1)
   10
   1 5 2 1 4 3 4 5 2 1
   
1. 수열의 A의 크기 N과 수열 A 입력
   N = 10
   arr = {1, 5, 2, 1, 4, 3, 4, 5, 2, 1}

2. 오름차순 부분수열 크기 구하기
   dp_asc = {1, 2, 2, 1, 3, 3, 4, 5, 2, 1}

3. 내림차순 부분수열 크기 구하기
   dp_dec = {1, 5, 2, 1, 4, 3, 3, 3, 2, 1}

4. 바이토닉 부분수열 크기 구하기(오름차순 부분수열 크기 + 내림차순 부분수열 크기 - 1)
   dp_bitonic = dp_asc + dp_dec - 1 (중복 방지를 위해 1을 빼줌)
   dp_bitonic = {1, 6, 3, 1, 6, 5, 6, 7, 3, 1}

5. 바이토닉 부분수열 크기 중 최댓값 구하기
   ans = 7

 

5.  유용한 문법 및 알고리즘

5 - 1) 오름차순 부분수열의 최대 크기 구하기

int N;
int arr[1000];

void solve() {
	for (int i = 0; i < N; i++) {
		int max_val = 0;
        
		for (int j = 0; j < i; j++)
			if (arr[j] < arr[i])
				max_val = max(max_val, dp_asc[j]);

		dp_asc[i] = max_val + 1;
	}
}

 

5 - 2) 내림차순 부분수열의 최대 크기 구하기

int N;
int arr[1000];

void solve() {
	for (int i = N - 1; i >= 0; i--) {
		int max_val = 0;

		for (int j = N - 1; j > i; j--)
			if (arr[j] < arr[i])
				max_val = max(max_val, dp_dec[j]);

		dp_dec[i] = max_val + 1;
	}
}