[백준] 자바 Java, 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 5 2 1 4 3 4 5 2 1}이 가장 긴 바이토닉 부분 수열이다.

 

 

알고리즘 분류

• 다이나믹 프로그래밍

 

나의 풀이

참고)

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

• 바이토닉(Bitonic) : 특정 값을 기준으로 왼쪽 부분은 오름차순, 오른쪽 부분은 내림차순인 수열 또는 그러한 부분 순환이동

참고)

[백준] 자바 Java, 11503번: 가장 긴 증가하는 부분 수열

• 11053번 문제를 풀고 풀 경우 쉽게 해결 가능

 

• Bottom-up 방식 사용

package level15_dynamicProgramming;

import java.util.Arrays;
import java.util.Scanner;

//백준 11053번 문제] 가장 긴 바이토닉 부분 수열
//바이토닉 :
public class Backjoon11054 {
    public static void main(String[] args) {
        //입력strat
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int arr[] = new int[n];
        int lisDp[] = new int[n];
        int ldsDp[] = new int[n];

        for(int i=0; i<n; i++) {
            arr[i] = sc.nextInt();
        }
        //입력end

        //LIS(최장 증가 부분수열)
        for(int i=0; i<n; i++) {
            lisDp[i] = 1;

            // 0부터 i 이전까지의 원소 비교!
            for (int j=0; j<i; j++) {
                // j번째 원소보다 작으면서 && lisDp[i]가 lisDp[j]+1(초기값이 1이기 때문에)보다 작은 경우
                if(arr[j] < arr[i] && lisDp[i] < lisDp[j] + 1) {
                    lisDp[i] = lisDp[j] + 1;
                }
            }

        }

        //LDS(최장 감소 부분수열)
        for(int i=n-1; i>=0; i--) {
            ldsDp[i] = 1;

            // 맨 뒤부터 i 이전까지의 원소 비교!
            for (int j=n-1; j>i; j--) {

                // i번째 원소가 j번째 원소보다 크면서 && ldsDp[i]가 ldsDp[j]+1 값보다 작은 경우
                if (arr[j] < arr[i] && ldsDp[i] < ldsDp[j] + 1) {
                    ldsDp[i] = ldsDp[j] + 1;
                }
            }
        }

        //최댓값 구하기
        int max[] = new int[n];
        for(int i=0; i<n; i++) {
            max[i] = lisDp[i] + ldsDp[i] - 1; //단순 더하기는 원소 1개가 중복되기 때문에 1 빼줘야 함
        }
        Arrays.sort(max);
        System.out.println(max[n-1]);
    }//main end
}

 

결과