백준 11054번 가장 긴 바이토닉 부분 수열(자바) - dp

가장 긴 바이토닉 부분 수열 

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

25046

12708

10022

51.332%

문제

수열 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

---

이 문제는 골드 문제여서 조금 어렵지 않을까 했지만 저번에 풀었던 가장 긴 증가하는 부분 수열 문제를 풀 수 있으면 어렵지 않게 풀 수 있었던 문제이다. 

2021.07.26 - [코딩테스트] - *백준 11053번 가장 긴 증가하는 부분 수열(자바) - dp

*백준 11053번 가장 긴 증가하는 부분 수열(자바) - dp

 

 

풀이 :

예를 들어 10 20 30 25 20 이라는 수열이 있다고 하자.

이때는 수열의 모든 수를 한번씩 기준으로 세우고 수의 왼쪽으로는 증가하는 가장 긴 부분 수열을 구하고, 오른쪽으로는 감소하는 가장 긴 부분 수열을 구하면 된다. 

 

즉, 첫 번째로 10을 기준으로 삼으면 10의 왼쪽에는 수가 없으므로 10까지의 증가하는 가장 긴 수열의 길이(dp[0][0]이라고 하자)는 1이고, 10부터 수열의 가장 끝 수인 20까지 10보다 작은 수가 없으므로 10부터 감소하는 가장 긴 수열의 길이(dp[0][1])는 1이다. 

 

마찬가지로 20도 기준으로 삼고 진행해준다.

하나 더 예시를 들어 30을 기준으로 하는 경우를 생각해보면

30의 왼쪽에는 10과 20이 있으므로 30까지 증가하는 긴 부분 수열의 길이는 3이고,

30부터 감소하는 가장 긴 부분 수열을 구하면 되는데 이때 더 쉽게 구하기 위해서 30 25 20이라는 수열을 반대로 뒤집어 20 25 30이라는 수열이라고 생각하고 증가하는 가장 긴 부분 수열을 구해준다. 그럼 이 길이도 3이 나온다. 이 때, 30은 기준이기 때문에 10 20 30을 세어줄 때와 20 25 30을 세어줄 때 두번 포함되므로 한 번을 빼준다.

즉, 3 + 3 - 1해서 30이 기준일 때 가장 긴 바이토닉 부분 수열의 길이는 5이다.

---

import java.util.Scanner;


public class Main {
   static int arr[];
   static int dp[][];
   static int sum[];
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        arr = new int[n];
        dp = new int[n][2];
        sum = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        int max = 1;
        for (int i = 0; i < n; i++) {
            dp[i][0] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && dp[i][0] <= dp[j][0]) {
                    dp[i][0] = dp[j][0] + 1;
                }
            }
            sum[i] += dp[i][0];
        }
        for (int i = n-1; i >= 0; i--) {
            dp[i][1] = 1;
            for (int j = n-1; j > i; j--) {
                if (arr[i] > arr[j] && dp[i][1] <= dp[j][1]) {
                    dp[i][1] = dp[j][1] + 1;
                }
            }
            sum[i] += dp[i][1];
            sum[i]--;
            max = Math.max(max, sum[i]);
        }
        System.out.println(max);

    }
}