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

www.acmicpc.net/problem/11054

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

 

1. 문제 설명

 

가장 긴 바이 토닉 수열의 길이를 구하는 문제이다.

 

바이 토닉 수열은 수열 S가 어떤 수 Sk를 기준으로 S1 < S2.. Sk-1 < Sk > Sk+1... > Sn을 만족하는 수열을 말한다.

 

가장 긴 증가하는 부분수열 문제를 풀었다면 어렵지 않게 해결할 수 있다.

 

왼쪽에서 시작해서 증가하는 부분 수열 문제를 풀고

 

오른쪽 끝에서 시작하여 증가하는 부분 수열 문제를 풀고 

 

두 문제를 합쳐서 제일 긴 바이토닉 수열의 길이를 찾으면 된다.

 

첫 번째 행이 주어진 수열, 두 번째 행이 왼쪽에서 증가하는 부분 수열의 길이(dp_right []), 세 번째 행이 오른쪽에서 증가하는 부분 수열의 길이를 구한 배열(dp_left [])이라고 한다면 아래와 같은 표가 만들어진다.

 

가장 긴 바이 토닉 수열은 Sk를 기준으로 dp_right [Sk]+dp_left [Sk]의 값이 가장 큰 수열이다.

 

1	5	2	1	4	3	4	5	2	1
1	2	2	1	3	3	4	5	2	1
1	4	2	1	3	3	3	3	2	1

 

 

 

 

 

2. 코드

 

import java.awt.image.BufferedImageFilter;
import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {



    public static void main(String[] args) throws IOException {
        Scanner scan=new Scanner(System.in);

        int num=scan.nextInt();

        int[] list=new int[num];
        int[] dp_right=new int[num];
        int[] dp_left=new int[num];

        int answer=0;

        dp_right[0]=dp_left[num-1]=1;

        for(int x=0;x<num;x++){
            list[x]=scan.nextInt();

            dp_right[x]=1;

            for(int y=0;y<x;y++){
                if(list[x]>list[y] && dp_right[x]<dp_right[y]+1)
                    dp_right[x]=dp_right[y]+1;
            }
        }

        for(int x=num-1;x>=0;x--){

            dp_left[x]=1;

            for(int y=num-1;y>x;y--){
                if(list[x]>list[y] && dp_left[x]<dp_left[y]+1)
                    dp_left[x]=dp_left[y]+1;
            }

            if(answer<dp_left[x]+dp_right[x])
                answer=dp_left[x]+dp_right[x];
        }

        System.out.println(answer-1);

        scan.close();


    }

}