Backjoon(백준) 11054 - 가장 긴 바이토닉 부분 수열(Java)

1. 풀이 힌트 

 - 백준 11053 - 가장 긴 증가하는 부분 수열과 비슷한 문제이다. 부분 수열을 고려 할 때, 증가하는 값과 이어지는 감소하는 값을 고려한 바이토닉 수열의 길이를 구해야 한다. 따라서 증가에서 감소로 가는 부분에서, 증가할 때 이어지던 수열의 길이를 감소할 때 이어서 카운트 해주어야 한다

2. 풀이 과정

 - 기본적으로 이전에 작성한 '가장 긴 증가하는 부분 수열의 풀이'를 기준으로 설명하겠다. 

1) 밑의 표와 같이 증가하는 부분 수열의 크기만을 기록한 기존의 dp 배열을 2차원으로 확장하여 저장된 값, 증가하는 부분의 수열의 크기, 감소하는 수열의 크기(+ 바이토닉 구간)을 저장하는 새로운 배열을 선언해야 한다 

표1) 증가하는 부분수열만 고려한 배열선언

arr (저장된 값)	10	20	10	30	20	50
dp (큰 순서)	1	2	1	3	2	4

표2) 2차원 배열 dp선언

dp[][0] 수열 값	10	20	10	30	20	50
dp[][1] > 값	1	2	1	3	2	4
dp[][2] < 값	1	1	3(2 + 1)	1	4(3 + 1)

2) 2차원 배열을 통해 증가값과 감소값을 저장하면서, 증가에서 감소로 넘어가는 부분(바이토닉 구간)은 기존에 증가하던 부분수열의 크기에서 감소하는 부분수열의 크기를 더해주어야 한다. 

3) 만약 수열이 증가에서 감소하는 부분없이 계속 감소하는 구조로 이루어져 있는 경우도 고려하여 dp[][2]의 값의 크기를 계속 유지해 준다.

4) 2)번과 3)번을 비교한 최대값이 최종적으로 dp[][2]의 크기가 된다.

5) 가장 긴 바이토닉 수열의 값은 dp[][1]의 최댓값과 dp[][2]의 최댓값중에 더 큰 값이다.

 

+ 제가 설명한 방법 말고 역방향으로 증가하는 부분수열을 계산하여 가장 긴 바이토닉 부분 수열을 구하는 더 간단한 풀이도 있습니다~ 인터넷에 검색해서 한번 찾아보시면 좋을거에요:)

3. 코드 구현

import java.util.Scanner;

// 11053 가장 긴 증가하는 부분 수열
public class Progression2 {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int max = 0;
        
        int[][] dp = new int[1001][3];
        
        for (int i = 1; i <= n; i++) {
            dp[i][0] = sc.nextInt();
            dp[i][1] = 1; dp[i][2] = 1;
            for (int j = 1; j < i; j++) {
                if (dp[i][0] > dp[j][0] && dp[j][1] >= dp[i][1]) {
                    dp[i][1]++;
                }
                if (dp[i][0] < dp[j][0]) {
                    dp[i][2] = Math.max(dp[i][2], dp[j][2] + 1);
                    dp[i][2] = Math.max(dp[i][2], dp[j][1] + 1);
                }
            }
            
            max = Math.max(max, Math.max(dp[i][1], dp[i][2]));
        }
        
        System.out.println(max);
    }

}