백준 11054번 - 가장 긴 바이토닉 부분 수열

 

 

 

 

* 문제 링크

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

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

 

 

 

문제 내용 요약

 

어떤 수 S_k 를 기준으로 S_1 부터 S_k 까지 증가, S_k 부터 S_n 까지 감소하는 형태면

 

바이토닉 부분 수열이라고 부른다.

 

수열이 주어지면 가장 긴 바이토닉 부분 수열의 길이를 구하여라.

 

 

 

 

 

 

접근법

 

일단은 이 문제를 풀기 전에 LIS 문제부터 풀고 오는 것을 추천한다.

 

https://syerco0.com/22

백준 11053번 - 가장 긴 증가하는 부분 수열 (LIS)

 

 

LIS 문제를 푸는 방법을 안다면, 비슷하게 생각하면 된다.

 

LIS 가 된다면, 반대로 가장 긴 감소하는 부분 수열(LDS라 칭할 수 있을 것)도 구할 수 있을 것이다.

 

그것들을 구하는데, 저장했던 값들이 뭐였는지 기억하는가?

 

"해당 번째의 값을 포함하여 구한 LIS/LDS 값"

 

 

이제 어떻게 하면 되는가?

 

그렇다. 두 가지 다 구해서 더해준 값 (에 1을 뺀 값이지만 비교에는 상관없다) 을 비교해주면 된다.

 

해당 번째의 값을 기준으로 왼쪽은 증가, 오른쪽은 감소하는 수열의 길이로 나타내어질 것이다.

 

그러면 간단히 가장 긴 바이토닉 부분 수열을 구할 수 있다.

 

더 이상의 자세한 설명은 생략한다.

 

 

 

 

내 코드

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

int arr[1005];
int n;
int len[1001];
int rlen[1001];

int main() {
    cin>>n;
    for(int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }
    for(int i=0;i<n;i++) {
    	len[i]=1;
    	for(int j=0;j<i;j++) {
    		if(arr[j]<arr[i]) len[i]=max(len[i],len[j]+1);
		}
	}
	for(int i=n-1;i>=0;i--) {
    	rlen[i]=1;
    	for(int j=n-1;j>i;j--) {
    		if(arr[j]<arr[i]) rlen[i]=max(rlen[i],rlen[j]+1);
		}
	}
	int mx=0;
	for(int i=0;i<n;i++) {
		mx=max(mx,len[i]+rlen[i]);
	}
	cout<<mx-1;
}

 

분명 중괄호 위치에 문제가 없는 코드인데, 여기에 올리니 위치가 이상해보인다. 왜지?