[알고리즘] 백준 11054 가장 긴 바이토닉 부분 수열 -dp-

https://www.acmicpc.net/problem/11054

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

 

 

 

 

백준의 가장 긴 바이토닉 부분 수열 문제를 풀어봤습니다.

동적계획법1 의 단계별문제이며 이전에 풀었던 문제에서 조금씩 응용을 하며 풀고 있습니다. 이 문제도 한가지의 케이스를 더 생각하고 응용하면 풀리는 문제였습니다.

이전문제는 다음 포스팅에서 참고합니다.

https://youngest-programming.tistory.com/265

[알고리즘] 백준 2156 포도주 시식 -dp-

https://youngest-programming.tistory.com/266

[알고리즘] 백준 11053 가장 긴 증가하는 부분 수열 -dp-

 

dp[0][] 에는 입력 숫자를 받습니다.

dp[1][] 에는 왼쪽에서 오른쪽으로 증가하는 부분수열 최대 길이를 받습니다.

dp[2][] 에는 오른쪽에서 왼쪽으로 증가하는 부분수열 최대 길이를 받습니다.

 

i를 돌며 dp[1][i] 과 dp[2][i] 를 더했을 때의 최댓값에서 겹치는 부분 -1 을 해준 값들 중 최댓값이 가장 긴 바이토닉 부분 수열 길이가 됩니다.

 

예제의 경우 {1 5 2 1 4 3 4 5 2 1}이 가장 긴 바이토닉 부분 수열이다. => 따라서 답은 7이다. 5가 Max Point 가 되고 중첩이 되므로 -1을 코드에서는 해줘야 합니다.

 

 

 

풀이는 다음과 같습니다.

import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] dp = new int[3][n + 1]; // n 번째까지의 최대 부분수열 길이
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            dp[0][i] = sc.nextInt();
        }

        // 왼쪽에서 오른쪽에 증가 부분수열 dp
        for (int i = 1; i <= n; i++) {
            int increaseCnt = 0;
            for (int j = 1; j <= i; j++) {
                if (increaseCnt < dp[1][j] && dp[0][i] > dp[0][j]) { // 과거(이전값들) 중 최대 부분수열 길이를 최우선으로하고, 그 때의 값보다 커야하는걸 만족해야함
                    increaseCnt = dp[1][j];
                }
            }
            dp[1][i] = increaseCnt + 1;
        }

        // 오른쪽에서 왼쪽으로 증가 부분수열 dp
        for (int i = n; i >= 1; i--) {
            int decreaseCnt = 0;
            for (int j = n; j >= i; j--) {
                if (decreaseCnt < dp[2][j] && dp[0][i] > dp[0][j]) { //오른쪽에서 왼쪾으로 갈수록 더커져야함 (위와 순서뺴고 동일)
                    decreaseCnt = dp[2][j];
                }
            }
            dp[2][i] = decreaseCnt + 1;
        }

        // 서로 개수 한개가 겹치므로 -1
        for (int i = 1; i <= n; i++) {
            answer = Math.max(answer, dp[1][i] + dp[2][i] - 1);
        }
        System.out.println(answer);
    }
}

 

 

공감은 큰 힘이 됩니다. 감사합니다!