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

klean·2020년 10월 8일
0

https://www.acmicpc.net/problem/11054
문제
수열 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다

아이디어

LIS, LDS에 대해 각 원소를 시작점/끝점으로 했을 때 길이를 memoization한다
단 LIS는 뒷 LIS들을 참조하며 이 원소가 앞머리에 붙어도 되는지를 검사하며 구한다.
단 각 LDS는 앞 LDS들을 참조하며 이 원소가 꼬리에 붙어도 되는지를 검사하며 구한다.
마지막에 각 원소에 대한 LIS+LDS-1이 가장 긴 바이토닉 수열의 길이이다.

코드

#include<iostream>
#include<algorithm>
using namespace std;
//lis lds 같이
int main() {
	int n;
	cin >> n;
	int *a = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int *b = new int[n];

	b[0] = 1;
    //lds구함
	for (int i = 0; i <= n - 1; i++) {
		b[i] = 1;
		for (int j = 0; j < i; j++) {
			if (a[j] < a[i]) {
				b[i] = max(b[i], b[j] + 1);
			}
			
		}
	}


	//뒤에서부터 작은 LiS 계산(나로부터 시작하는)
	int *c = new int[n];


	c[n - 1] = 1;


	for (int i = n - 1; i >= 0; i--) {
		int diff = n - 1 - i;//i== n-2면 diff==1

		c[i] = 1;//나 자신이 b[i]인 경우
		
		for (int j = 1; j <= diff; j++) {
			//b[i+j]중 나랑 매치되는 것 중 가장 큰 것 찾기
			//만약 못찾는다면 나 자신이 b[i]가 된다
			if (a[i + j] < a[i]) {
				c[i] = max(c[i], c[i + j] + 1);
			}
		}
	}
	int res = 0;
	
	for (int i = 0; i < n; i++) {
		res = max(res, b[i] + c[i]-1);
	}

	cout << res << endl;

	/*
	for (int i = n - 1; i >= 0; i--) {
		cout << "i는 \t" << i << "\t" << b[i] << "\t"<<c[i]<< endl;
		
	}
	*/
	
	//b[0]가 답이 아니다!!!!
	delete[] a;
	delete[] b;
	delete[] c;
}

0개의 댓글