[Algorithm] 백준_가장 긴 바이토닉 부분 수열_11054번 (JAVA)

📝문제

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

---

💡풀이

문제 유형

다이나믹 프로그래밍

 

걸린 시간

15분

 

시간 복잡도

O(N^2)

 

풀이 방법 도출

1. 이 문제를 풀기 전 가장 긴 증가하는 부분 수열(https://www.acmicpc.net/problem/11053), 가장 긴 감소하는 부분 수열(https://www.acmicpc.net/problem/11722) 이 문제들을 풀고 오면 풀이가 쉬워진다.
2. 위 두 문제를 짬뽕해 놓은 문제가 "가장 긴 바이토닉 부분 수열"이기 때문!!
3. 먼저 증가하는 부분 수열의 길이를 dp에 담는다.
4. 현재 위치와 다음 위치부터 N-1번째 위치까지의 수를 비교하여 현재 위치의 수보다 다음 위치의 수가 더 크다면 다음 위치의 dp를 갱신해 준다.
5. 기본적으로 현재 dp값+1이 다음 위치의 dp값이 되지만 기존 저장된 dp값이 더 큰 경우가 있으므로 비교 후 갱신해 준다.
6. 그럼 증가수열은 1,2,2,1,3,3,4,5,2,1 이 dp에 들어갈 것이다.
7. 이후 감소하는 부분 수열의 길이를 기존 값과 비교하여 넣어준다.
8. 이제 가장 큰 값을 가지는 수를 찾아 답을 도출한다.

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            A[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[N];
        Arrays.fill(dp, 1);
        for(int i = 0; i < N; i++){
            for(int j = i+1; j < N; j++){
                if(A[j] > A[i]){
                    dp[j] = Math.max(dp[j], dp[i]+1);
                }
            }
        }

        for(int i = 0; i < N; i++){
            for(int j = i+1; j < N; j++){
                if(A[j] < A[i]){
                    dp[j] = Math.max(dp[j], dp[i]+1);
                }
            }
        }

        int len = 0;
        for(int d : dp){
            len = Math.max(d, len);
        }

        System.out.println(len);
    }
}

---

🤔Review

응용문제를 풀기 전 기본 문제로 연습을 하니 문제 풀이가 훨씬 수월해졌다 역시 알고리즘 유형은 많이 풀어볼수록 유리한 거 같다.