백준 : 가장 긴 바이토닉 부분 수열(11054) with 자바

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

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

배열의 크기 N, 배열 dp[]가 주어졌을 때 가장 긴 바이토닉 수열의 값을 구하는 문제이다.

예제를 살펴보자

dp의 값은 이전값이 현재값보다 작을 때 + 1을 해주면된다.

바이토닉 수열의 최댓값을 구하기 위해서는 dp[]배열의 (왼쪽 -> 오른쪽) + (오른쪽 -> 왼쪽)을 해서 최댓값을 출력해주면 된다.

그러므로 우린 dp[]를 입력 받고 좌 -> 우를 순환하여 수열의 값을 찾고, 우 -> 좌를 순환하여 수열을 값을 찾은 뒤에 두 배열의 값을 합쳐서 가장 긴 수열의 길이를 찾아줄 것이다.

 

그럼이제 코드를 살펴보자.

public static void main(String[] args){

      Scanner sc = new Scanner(System.in);

      int N = sc.nextInt();

      int[] dp = new int[N + 1];

      int[] LRdp = new int[N + 1];

      int[] RLdp = new int[N + 1];

      int res = 0;

      for(int i=1; i <= N; i++){

            dp[i] = sc.nextInt();

      }

      // 좌 -> 우

      for(int i=1; i <=N; i++){

            LRdp[i] = 1;

            for(int j=1; j < i; j++){

                   if(dp[i] > dp[j]){

                       LRdp[i] = Math.max(LRdp[j] + 1, LRdp[i]);

                   }

            }

       }

       // 우 -> 좌

       for(int i=N; i >= 1; i--){

             RLdp[i] = 1;

             for(int j=N; j > i; j--){

                   if(dp[i] > dp[j]){

                       RLdp[i] = Math.max(RLdp[j] + 1, RLdp[i]);

                   }

             }

       }

       for(int i=1; i <= N; i++){

              res = Math.max(res, LRdp[i] + RLdp[i] - 1); // 중복요소 1 제거

       }

       System.out.println(res);

}

코드를 하나하나 살펴보자

스캐너 객체를 생성한뒤 수열의 크기 N을 입력받는다.

수열을 저장할 dp[], 좌 -> 우를 순환할 LRdp[], 우 -> 좌를 순환할 RL[]dp, 결과값을 저장할 res를 선언하였다.

반복문을 사용하여 수열안에 들어갈 숫자를 입력받았다.

좌에서 우로 순환하며 수열을 저장할 반복문이다. 첫 노드부터 시작하므로 i = 1을 할당하였고 i++를 해준다.

LRdp[i] = 1로 시작값을 할당한 뒤 이전값 + 1과 현재값을 비교하여 최댓값을 LRdp[i]에 저장한다.

우에서 좌로 순환하며 수열을 저장할 반복문이다. 끝에서 부터 시작하므로 i = N을 할당하였고 i--를 해준다.

나머지는 좌에서 우로 순환하는 코드와 마찬가지로 최댓값을 구해주면 된다.

마지막으로 (왼쪽 -> 오른쪽) + (오른쪽 -> 왼쪽)을 순환하여 구한값을 구해주면 된다.

순환하는 과정에서 중복되는 요소를 반드시 제거해주어야한다. 그래서 LRdp[i] + RLdp[i] - 1을 해서 중복요소를 제거해주었다.

res를 출력하면 가장긴 바이토닉 수열을 구할 수 있을 것이다.