[백준] 11054 가장 긴 바이토닉 부분 수열 + 11053 가장 긴 증가하는 부분수열 + lower_bound

문제

수열 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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

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

 

출력

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

#include<bits/stdc++.h>
using namespace std;

int n, x, dp[1001], dp2[1001], arr[1001]; //dp는 증가하는 수열의 길이 ,dp2는 감소하는 수열의 길이를 저장
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
    //1~n번까지 가장 긴 수열의 길이를 구함
	for (int i = 1; i <= n; i++) {
		int v = 1;
		for (int j = 1; j <= i; j++) {
			if (arr[i] > arr[j]) {
				v = max(v, dp[j]+1);
			}
		}
		dp[i] = v;
	}
    //i부터 n번까지 가장 긴 수열의 길이를 구함
	for (int i = n; i >= 1; i--) {
		int v = 1;
		for (int j = n; j >= i; j--) {
			if (arr[i] > arr[j]) {
				v = max(v, dp2[j] + 1);
			}
		}
		dp2[i] = v;
	}
	int ans = -1;
	for (int i = 1; i <= n; i++) {
		ans = max(ans, dp[i] + dp2[i]);
	}
	cout << ans - 1;
}

 

 

골드4 DP문제입니다

1~n번 숫자중 i번째 숫자를 기준으로 1~i번 가장 긴 증가하는 부분수열, i~n번 가장 긴 감소하는 부분수열의 길이를 더하고 1을 빼면 정답입니다.

 

 

 

가장 긴 증가하는 부분수열을 구하는 알고리즘은 다음과 같습니다.

dp[k]는 i:1~k중에 arr[k]<arr[i]이면서, dp[i]중 가장 큰값+1입니다.

 

하지만 

lower_bound를 사용하면 더 짧게 구할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int arr[1001], idx, t;
int main() {
	int	n, x;
	cin >> n;
	while (n--) {
		cin >> x;
		idx = lower_bound(arr, arr + t, x)-arr; //새로 입력한 숫자 x가 들어갈 자리를 찾습니다
        //lower bound는 x보다 크거나 같은 가장 작은 배열요소의 iterator을 반환합니다.
		arr[idx] = x; //구한 인덱스에 x값을 대입합니다.
        //1. 만약 x가 가장 큰수라면, x는 가장 마지막에 입력됩니다. idx는 t와 같습니다. 그리고 t++
		if (idx >= t)t++;
      
        //2. 만약 x가 가장 큰수는 아니라면, x는 중간에 입력됩니다. idx는 t보다 작습니다.
	}
	cout << t;
}