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

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

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

 

import java.util.Scanner;

public class BJ_11054_2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] A = new int[n + 1];
        int[][] dp = new int[2][n + 1];
        int max = 0;

        for (int i = 1; i < n + 1; i++) {
            A[i] = scan.nextInt();
        }

        for (int i = 1; i < n + 1; i++) {
            dp[0][i] = 1;

            for (int j = 1; j < i; j++) {
                if (A[i] > A[j] && dp[0][i] <= dp[0][j]) {
                    dp[0][i] = dp[0][j] + 1;
                }
            }
        }

        for (int i = n; i > 0; i--) {
            dp[1][i] = 1;

            for (int j = n; j > i; j--) {
                if (A[i] > A[j] && dp[1][i] <= dp[1][j]) {
                    dp[1][i] = dp[1][j] + 1;
                }
            }
        }

        for (int i = 1; i < n + 1; i++) {
            dp[0][i] += dp[1][i];
        }

        for (int i = 1; i < n + 1; i++) {
            if (max < dp[0][i]) {
                max = dp[0][i];
            }
        }

        System.out.println(max - 1);
    }
}

 

DP 문제이다. 

 

2차원 배열 dp를 통해 문제를 해결하였다.

 

처음에는 가장 왼쪽에서 시작하는 증가하는 가장 긴 부분수열과 그 다음 인덱스부터 해서 시작하는 가장 긴 부분수열을 오른쪽 끝까지 구하는 방식으로 풀어 정답을 구하였다.

 

근데 그렇게하니 다른 정답과 비교했을때 시간효율이 너무 낮아서 다른분 코드를 참고하여 위와 같이 리팩토링 하였다.

 

dp[0][i]에는 왼쪽부터 시작하는 증가하는 가장 긴 부분 수열,

 

dp[1][i]에는 오른쪽부터 시작하는 증가하는 가장 긴 부분 수열이 들어간다.

 

위와 같은 방식을 사용할 수 있는 이유를 설명해보면

 

dp[0]은 1 ~ n까지의 부분수열, dp[1]은 n ~ 1까지의 부분수열이 들어간다.

 

즉 dp[0][i]은 1 ~ i까지의 부분수열, dp[1][i]는 n ~ i까지의 부분수열이 들어간다고 볼 수 있다.

 

그러므로 dp[0][i] += dp[1][i]를 연산하면 바이토닉 부분 수열의 규칙을 만족한다. 단 i가 겹치니 1빼줘야한다...

 

 정답은 가장 긴 바이토닉 부분 수열을 요구하므로  dp[0][i]의 최대값을 구하면 된다. 구하고 1 빼줘야 정답!!!