BOJ - 11054번 가장 긴 바이토닉 부분 수열, 동적계획법 문제

이번 문제는 동적 계획법(Dynamic programming)을 활용해 쉽게 풀이할 수 있는 문제입니다. 가장 긴 증가하는 부분 수열 구하기 + 가장 긴 감소하는 부분 수열 구하기 문제를 합친 문제라고 볼 수 있습니다!

 

0. 문제 링크

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

 

 

1. 문제 설명

 

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

2. 입력

 

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

 

3. 출력

 

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

4. 풀이 과정 및 생각했던 부분

 

이 문제는 오랜만에 동적 계획법 문제를 풀이하고 싶어 풀게 되었고, 2차원 배열을 이용해 memoization을 진행한다는 점을 고려해도 쉽게 풀이할 수 있었습니다.

 

우선 2차원 배열을 사용하는 이유는 배열의 각 숫자의 입장에서 현재 숫자를 포함했을 때 만들어지는 가장 긴 증가하는 부분 수열과 감소하는 부분 수열을 같이 기록하며 풀이해야 하기 때문입니다.

가장 긴 증가하는 부분 수열을 위 예시에 따라 구하는 pseudo code를 간단히 작성해보면, 다음과 같습니다.

10
1 5 2 1 4 3 4 5 2 1

dp[0](1) = 0
dp[1](5) = 1
dp[2](2) = 1
dp[3](1) = 0
...

// 가장 긴 증가하는 부분 수열을 매 위치에서 갱신
for(i = 0; i < end of array; i++){
	for(j = 0; j < i; j++){
    	if(arr[i] > arr[j]){
        	dp[i] = dp[i] or dp[j] + 1 중 큰 값;
        }
    }
}

이제 위 코드를 가장 긴 감소하는 부분 수열을 함께 구하도록 확장하면 다음과 같이 작성할 수 있게 됩니다.

dp[][2] => 0차원 column은 가장 긴 증가하는 부분 수열의 길이, 1차원은 가장 긴 감소하는 부분 수열의 길이를 저장

for(i = 0; i < end of array; i++){
	for(j = 0; j < i; j++){
    	if(arr[i] > arr[j]){
        	dp[i][0] = dp[i][0] or dp[j][0] + 1 중 큰 값;
        }
    }
}

for(i = end of array; i >= 0; i--){
	for(j = end of array; j > i; j--){
    	if(arr[i] > arr[j]){
        	dp[i][1] = dp[i][1] or dp[j][1] + 1 중 큰 값
        }
    }
}

이렇게 되면, 가장 긴 바이토닉 부분 수열의 길이는 dp[][0] + dp[][1] + 1(자기 자신)을 이용해 구할 수 있게 됩니다. 

 

5. 소스 코드 (with cpp)

/*
	Date: 2022/08/16
	Brief:
	Dynamic programming
	Reference:
*/
#include <iostream>
#include <algorithm>
#define MAX 1001

using namespace std;

int n;
int dp[MAX][2];
int arr[MAX];

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

	cin >> n;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) {
				dp[i][0] = max(dp[i][0], dp[j][0] + 1);
			}
		}
	}

	for (int i = n - 1; i >= 0; i--) {
		for (int j = n - 1; j > i; j--) {
			if (arr[i] > arr[j]) {
				dp[i][1] = max(dp[i][1], dp[j][1] + 1);
			}
		}
	}

	int res = 0;

	for (int i = 0; i < n; i++) {
		// 자기 자신까지 길이에 포함시켜야 한다.
		res = max(res, dp[i][0] + dp[i][1] + 1);
	}

	cout << res << "\n";

	return 0;
}

/*
두 개의 파트로 나눠서 dp로 구현해야
1. 증가하는 입장에서 기록하며
2. 감소하는 입장에서 기록하며

두 개를 합쳐서 가장 큰 값을 갖는 부분을 뽑는다.
*/