[백준(baekjoon) 11054] 가장 긴 바이토닉 부분 수열

문제

백준 11054

n(1…1,000)과 n의 크기를 가진 수열이 주어질 때,
바이토닉 부분 수열 중 가장 긴 길이를 출력.

• 바이토닉 수열 : S1 < S2 < … Sk-1 < Sk > Sk+1 > … SN-1 > SN을 만족하는 수열
• 예시 : {10, 20, 30, 25, 20}, {10, 20, 30, 40}, {50, 40, 25, 10}
• 주의 : 증가, 감소 수열도 바이토닉 수열에 속한다.

해결

가장 긴 증가하는 부분과 매우 유사한 문제이다.

2중 for문의 형태이고, 시간 복잡도는 O(n^2)이다.
최대 1000 * 1000 = 1,000,000이 되고, 1초(1억)을 넘지 않는다.

여기서 다른 점은, 증가하는 부분과 감소하는 부분 두 가지 모두 확인해야 한다는 점이다.

• 증가
  
  • 자신이 더 클 경우 증가.
  • 이전 증가하는 수열 길이만 확인하면 된다.
    
    • 증가하는 수열 -> 증가하는 수열
• 감소
  
  • 자신이 더 작을 경우 감소 가능.
  • 증가하는 수열과 감소하는 수열 모두 확인해야 한다.
    
    • 증가하는 수열 -> (증가 + 감소) 바이토닉 수열
    • 감소하는 수열 -> 감소하는 수열

알고리즘

DP로 풀었고, bottom-up 방식으로만 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.
7.        int n = sc.nextInt();
8.        int[][] dp = new int[n][3]; // 0: vaule, 1: length(<), 2: length(>)
9.        int maxLength = 1;
10.
11.        for (int i = 0; i < n; i++) {
12.            int v = sc.nextInt();
13.            dp[i][0] = v;
14.            dp[i][1] = 1; dp[i][2] = 1;
15.            for (int j = 0; j < i; j++) {
16.                if (dp[j][0] < v)
17.                    dp[i][1] = Math.max(dp[i][1], dp[j][1] + 1);
18.                if (dp[j][0] > v) {
19.                    dp[i][2] = Math.max(dp[i][2], dp[j][2] + 1);
20.                    dp[i][2] = Math.max(dp[i][2], dp[j][1] + 1);
21.                }
22.            }
23.            maxLength = Math.max(maxLength, Math.max(dp[i][1], dp[i][2]));
24.        }
25.        System.out.println(maxLength);
26.    }
27.}

결과