(14) [C, C++, Java] 백준 No.11054 : 가장 긴 바이토닉 부분 수열

문제

풀이

자세한 풀이 : https://ldgeao99.tistory.com/entry/챕터3-15-DP-문제-풀이3-4-백준-No11054-가장-긴-바이토닉-부분-수열

 

# C++

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<int> d1(n);
    vector<int> d2(n);

    for (int i = 0; i < n; i++)
        cin >> a[i];


    // 왼->오 순으로 A[i]를 원소로 포함하는 가장 긴 증가하는 부분 수열의 길이 구하기
    for (int i = 0; i < n; i++)
    {
        d1[i] = 1;

        for (int j = 0 ; j < n; j++)
        {
            if (a[j] < a[i] && d1[i] < d1[j]+1)
                d1[i] = d1[j]+1;
        }
    }

    // 오->왼 순으로 A[i]를 원소로 포함하는 가장 긴 증가하는 부분 수열의 길이 구하기
    for (int i = n-1; i >= 0; i--)
    {
        d2[i] = 1;

        for (int j = n-1 ; j > i; j--)
        {
            if (a[j] < a[i] && d2[i] < d2[j]+1)
                d2[i] = d2[j]+1;
        }
    }


    // d1[i] + d2[i] - 1 의 최대값 찾기
    int ans = d1[0] + d2[0] - 1;
    
    for (int i = 0; i < n; i++)
    {
        if (ans < d1[i] + d2[i] - 1)
            ans = d1[i] + d2[i] - 1;
    }

    cout << ans << "\n";
}

# C

#include <stdio.h>
int a[1000];
int d[1000];
int d2[1000];
int main() {
    int n;
    scanf("%d",&n);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
    }
    for (int i=0; i<n; i++) {
        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--) {
        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;
        }
    }

    printf("%d\n",ans);
    return 0;
}

 

# Java

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i=0; i<n; i++) {
            a[i] = sc.nextInt();
        }
        int[] d = new int[n];
        for (int i=0; i<n; i++) {
            d[i] = 1;
            for (int j=0; j<i; j++) {
                if (a[j] < a[i] && d[i] < d[j]+1) {
                    d[i] = d[j]+1;
                }
            }
        }
        int[] d2 = new int[n];
        for (int i=n-1; i>=0; i--) {
            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 = d[0]+d2[0]-1;
        for (int i=0; i<n; i++) {
            if (ans < d[i]+d2[i]-1) {
                ans = d[i]+d2[i]-1;
            }
        }
        System.out.println(ans);
    }
}