[DP] 백준 문제 풀이 - 11054 가장 긴 바이토닉 부분 수열

👩🏻‍💻 문제링크

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

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

 

✍️ 아이디어

1. 문제 이해

• 저점에서 올라갔다가 최고점 찍고 내려오는 최대 긴 수열의 항의 갯수를 구하는것임  (∧ 이런 크기로 수열이 정렬되어야함)

2. 나는 2차원 배열을 이용하여 배열의 한 요소가 내려가는 중인 경우와 올라가는 중인 경우를 나눠서

1) 올라가는 중인 경우 : 자신 보다 작은 수랑만 비교 할수 있음

2) 내려가는 중인 경우 : 자신보다 작고 큰수 둘다 비교 할수 있음 

 

 

✍️소스코드

• 난 조금 복잡하게 푼 편인듯

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

int result[1001][2]; //[1]은 내려가는 경우 [2]는 올라가는 경우이다
int a[1001];
int main()
{
	int n; cin>>n;
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=2; j++)
		{
			result[i][j]=1;//배열 전체 1로 초기화
		}
	}
	for(int i=1; i<=n; i++)
	{
		int max1=0, max2=0;
		for(int j=i; j>0; j--)
		{
			if(a[j]>a[i]) // 배열의 요소가 내려가는 중인경우
			{
				if(max1<result[j][1]) // 올라가는 경우에서 max 찾음 (산 올라가서 꺾임 ∧)
					max1=result[j][1];
				if(max1<result[j][2]) // 내려가는 경우에서 max 찾음 (산 내려가는 중 ∧)
					max1=result[j][2];
			}
			else if(a[j]<a[i] && max2<result[j][2]) 
            // 배열의 요소가 올라가는 중인 경우는 무조건 자신보다 작은 수만 골라야함 (산 올라가는중 ∧)
			{
				max2=result[j][2];
			}
		}
		result[i][1]=max1+1;
		result[i][2]=max2+1;
	}
	int max=0;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=2; j++)
		{
			if(max<result[i][j])
				max=result[i][j];
		}
	}
	cout<<max<<'\n';
}

 

• 다 이렇게 풀었는데 증가수열의 최대 길이값 + 감소 수열의 최대 길이값을 더하였다 (아이디어!)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; i++) {
        cin >> a[i]; //1 5 2 1 4 3 4 5 2 1 
    }
    vector<int> d(n);//증가수열 저장	
    vector<int> d2(n);//감소수열 저장
    for (int i=0; i<n; i++) { //증가수열 구하기 1 2 2 1 3 3 4 5 2 1
        d[i] = 1;
        for (int j=0; j<i; j++) {
            if (a[j] < a[i] && d[j]+1 > d[i]) {
                d[i] = d[j]+1;
            }
        }
    }
    for (int i=n-1; i>=0; i--) { //감소 수열 구하기 1 5 2 1 4 3 3 3 2 1 
        d2[i] = 1;
        for (int j=i+1; j<n; j++) {
            if (a[i] > a[j] && d2[j]+1 > d2[i]) {
                d2[i] = d2[j]+1;
            }
        }
    }
    int ans = 0; 
    for (int i=0; i<n; i++) { //증가수열 + 감소수열의 최댓값 구함
        if (ans < d[i]+d2[i]-1) {
            ans = d[i]+d2[i]-1;
        }
    }

    cout << ans << '\n';
    return 0;
}

 

체감난이도	걸린시간	참고	사용 문법
중	30min	x	DP