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

이게 왜 안돼를 무수히 반복한 의지의 한국인

문제

풀이

최근에 LIS(가장긴증가하는부분수열) 문제를 푼 적이 있기때문에 아이디어 자체는 꽤 빠르게 생각해냈다.
가장 긴 증가하는 부분수열과 반대로 감소하는 부분수열의 길이를 합치면 된다.

그래서 처음엔 직접 binary search 코드를 작성해서 인덱스를 조절하고 문제 코드를 구성하였는데, 계속 오류가 났다. 그래서 그냥 지우고 다시 짰다.

인터넷 풀이는 O(n^2)으로 LIS를 푸는 코드를 활용했는데, 그냥 뭔가 내가 풀던 방식으로 풀어버리고 싶었다.

LIS를 다시 찾아보던 도중 엄청 간편한 함수를 알아냈다.
lower_bound() 함수이다.
이 함수를 이용하면 깔끔하게 binary search를 하고 해당 값이 들어갈 인덱스를 찾을 수 있다!
binary search 까지는 쉬운데 값이 어디에 들어갈지 생각하는 것 때문에 머리가 계속 복잡했는데 너무 명확해졌다.

두 번째로 배운 건 배열을 계속 새로 생성하는 것이 아니라
(첫 시도 때 vector를 clear하고 다시 쓰고 하는 식으로 했는데 여기서도 계속 오류가 발생했었다)
미리 만들어두고, len과 pos를 조절해가면서 배열을 재사용하는 방식이다.

그럼에도 불구하고 정답이 41퍼에서 틀렸다고 계속 나와서 그냥 미뤄버리려다가 오기가 생겨서 계속 봤다.

13
1 2 2 1 5 4 7 8 8 5 2 5 1
이렇게 바이토닉 수열의 기준점이 되는 지점에서 수가 겹치게 되면, 오버카운팅 되는 케이스를 고려하지 못했다.
i번째 전까지 증가하는 수 + i번째 포함 감소하는 수 로 카운트하면 될 거라고 생각했기 때문.

if(inc[lenInc-1] == (-decr[0])) lenInc--;

조건식을 추가해서 해결하였다.

코드

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


int a[1001];
int inc[1001];
int decr[1001];
int main(){
	
	freopen("input.txt", "r", stdin);
	int n, ans =0;
	cin>>n;
	
	for(int i=0; i<n; i++){
		cin>>a[i];
	}
	int pos = 0, lenInc =0, lenDec=0, tmp;
	for(int i=0; i<n; i++){
		
		lenInc = 0;
		for(int j=0; j<i; j++){
			pos = lower_bound(inc, inc+lenInc, a[j])-inc;
			inc[pos] = a[j];
			if(pos == lenInc) lenInc++;
		}
		 
		lenDec = 1;
		decr[0] = -a[i];
		for(int j=i+1; j<n; j++){
			pos = lower_bound(decr, decr+lenDec, -a[j])-decr;
			decr[pos] = -a[j];
			if(pos == lenDec) lenDec++;
		}
		if(inc[lenInc-1] == (-decr[0])) lenInc--;		
		if(ans<lenInc+lenDec) {
			ans = lenInc+lenDec;
			
		}
	}
	
	cout<<ans;
	return 0;
}