[백준11054] 가장 긴 바이토닉 부분 수열(LBS) / Java

문제주소 :www.acmicpc.net/problem/11054

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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력 1

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1

7

힌트

예제의 경우 {1 5 2 1 4 3 4 5 2 1}이 가장 긴 바이토닉 부분 수열이다.

 

<풀이법>

▒ 한줄 개념: 동적 계획법 ▒ 

>>[백준11053] 가장 긴 증가하는 부분 수열 (LIS) / Java<<보러가기

가장 기본적인 LIS 문제를 조금 응용하면 되는 문제입니다. 기본 LIS 문제에서는 한쪽 방향으로 증가하는 배열을 찾는다면, 이번에는 단순히 반복문의 순서를 조금 늘려서 가운데를 기준으로 양쪽으로 감소하는 배열을 찾는 것입니다.

또한 마지막에 정답값을 얻기 위해 i를 기준으로 양쪽의 길이를 세서 더해서 가장 큰 값을 비교해서 얻어냅니다.

 

 

<코드(Java)>

package Baekjoon;

import java.util.Scanner;

public class _11054_LBS {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int answer;
        int size = sc.nextInt();
        int[] arr = new int[size];
        int[] in_dp = new int[size];
        int[] de_dp = new int[size];


        for(int i = 0 ; i < size; i++){
            arr[i] = sc.nextInt();
            in_dp[i] = 1;
            de_dp[i] = 1;
        }

        for(int i = 0 ; i < size; i++){
            for(int j = 0; j < i; j++){
                if(arr[i] > arr[j])
                    in_dp[i] = max(in_dp[i], in_dp[j]+1);
            }
        }

        for(int i = size-1 ; i > -1; i--){
            for(int j = size-1 ; j > i; j--){
                if(arr[i] > arr[j])
                    de_dp[i] = max(de_dp[i], de_dp[j]+1);
            }
        }

        answer = 1;
        for(int i = 0; i < size; i++){
            if(in_dp[i] + de_dp[i] - 1 > answer){
                answer = in_dp[i] + de_dp[i] - 1;
            }
        }

        System.out.println(answer);
    }

    static int max(int a, int b){
        return a > b ? a : b;
    }
}

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest