[백준] 11054번 : 가장 긴 바이토닉 부분 수열

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

# 문제

 

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

# 입력

 

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

 

# 출력

 

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

# 예시 입력

10
1 5 2 1 4 3 4 5 2 1

# 예시 출력

7

---

[동적 프로그래밍]

저번에 풀었던 '가장 긴 증가하는 부분 수열' 문제에서 몇 가지만 추가 작업 해주면 된다.

2021/01/16 - [Programming/백준] - [백준] 11053번 : 가장 긴 증가하는 부분 수열

[백준] 11053번 : 가장 긴 증가하는 부분 수열

일반 바이토닉 부분 수열에 대해서 알아야 문제를 풀 수 있을 것 같다. 쉽게 말해서 임의의 수 i와 수열 arr에 대해서

 

증가하는 수열 <== arr[i] ==> 감소하는 수열

 

arr[i]를 기준으로 좌측은 arr[i]보다 작으면서 증가하는 수열,

arr[i]를 기준으로 우측은 arr[i]보다 작으면서 감소하는 수열이다.

 

빨간색 : 증가하는 부분 수열

노란색 : 기준

파란색 : 감소하는 부분 수열

{1 5 4 2 3} = 4

{1 2 4 3 2 4 1} = 6

{3 2 1 4 5 6} = 4

 

내가 적용한 알고리즘은 위에서 언급한 '가장 긴 증가하는 부분 수열'에서 쓰였던 알고리즘을 응용해서 했기 때문에 해당 알고리즘에 대해서는 위의 포스팅을 참고하길 바란다. (이하 LIS)

 

{3 2 1 4 5 6}이라는 수열을 가지고 예를 들어보자.

 

 

3    →    6

{3 2 1 4 5 6}

3    ←    6

위 표현이 무슨 의미인가? LIS를 2번 구하겠다는 말이다.

왼쪽에서 오른쪽으로 진행하며 LIS를 구하면 가장 긴 증가 부분 수열을 구할 수 있다.        --- (1)

오른쪽에서 왼쪽으로 진행하며 LIS를 구하면 또한 가장 긴 증가 부분 수열을 구할 수 있다. --- (2)

 

(1)과 (2)는 서로 상반된다. 즉 (2)는 위의 수열을 뒤집어서 LIS를 구한 것 이다. 핵심을 말하자면 (1)에게 있어 (2)는 감소수열이라고 할 수 있다. 글로써 설명하자니 읽는 사람도 쓰는 사람도 힘들다...

---

* idx = 1

idx	1	2	3	4	5	6
arr	3	2	1	4	5	6
DP_1	1
DP_2						1

X_1 = [3]

X_2 = [6]

---

* idx = 2

idx	1	2	3	4	5	6
arr	3	2	1	4	5	6
DP_1	1	1
DP_2					1	1

X_1 = [2]

X_2 = [5]

---

* idx = 3

idx	1	2	3	4	5	6
arr	3	2	1	4	5	6
DP_1	1	1	1
DP_2				1	1	1

X_1 = [1]

X_2 = [4]

---

* idx = 4

idx	1	2	3	4	5	6
arr	3	2	1	4	5	6
DP_1	1	1	1	2
DP_2			1	1	1	1

X_1 = [1, 4]

X_2 = [1]

---

* idx = 5

idx	1	2	3	4	5	6
arr	3	2	1	4	5	6
DP_1	1	1	1	2	3
DP_2		2	1	1	1	1

X_1 = [1, 4, 5]

X_2 = [1, 2]

---

* idx = 6

idx	1	2	3	4	5	6
arr	3	2	1	4	5	6
DP_1	1	1	1	2	3	4
DP_2	3	2	1	1	1	1

X_1 = [1, 4, 5, 6]

X_2 = [1, 2, 3]

---

왼쪽에서의 LIS와 오른쪽에서의 LIS를 모두 구했다. 우리가 구하고자 하는 것은 가장 긴 바이토닉 부분 수열 이므로,

(DP_1[i] + DP_2[i] -1)의 값이 최대인 곳을 찾으면 된다. 1을 빼는 이유는, i번 째 인덱스의 숫자가 중복되어 들어가기 때문이다.

* DP_1[6] = (1 - 4 - 5 - 6) 4

* DP_2[6] = (6)               1 (+)

-----------------------------------

Answer = (1 - 4 - 5 - 6 - 6) 5

가 되므로 -1을 빼서 중복된 수를 제거해주어야한다.

 

# Whole Code </> - Java 11

public class Main {

    static int[] arr = new int[1001];

    static int getAnswer(int x){

        int[][] result = new int[2][x+1];
        int[][] X = new int[2][x+1];

        int max = 1, i, j, z;

        X[0][1] = arr[1]; X[1][1] = arr[x];
        result[0][1] = 1;
        result[1][x] = 1;
        if(x > 1)
            for(i=2, j=x-1; i<=x; i++, j--){
                //왼쪽 -> 오른쪽 LIS
                for(z=1; X[0][z] != 0; z++)
                    if(arr[i] == X[0][z]){
                    
                        result[0][i] = z;
                        break;
                    }
                    else if(arr[i] < X[0][z]){
                    
                        result[0][i] = z;
                        X[0][z] = arr[i];
                        break;
                    }
                    else{
                    
                        result[0][i] = z + 1;
                        if(X[0][z+1] == 0){
                            X[0][z+1] = arr[i];
                        }
                    }
                //오른쪽 -> 왼쪽 LIS
                for(z=1; X[1][z] != 0; z++)
                    if(arr[j] == X[1][z]){
                    
                        result[1][j] = z;
                        break;
                    }
                    else if(arr[j] < X[1][z]){
                    
                        result[1][j] = z;
                        X[1][z] = arr[j];
                        break;
                    }
                    else{
                    
                        result[1][j] = z + 1;
                        if(X[1][z+1] == 0){
                            X[1][z+1] = arr[j];
                        }
                    }
            }
            
        //DP_1[i] + DP_2[i] - 1의 최대값 구하기
        for(i=1; i<=x; i++)
            max = Math.max(max, result[0][i] + result[1][i] - 1);
            
/*
//Debug code
        for(i=1; i<=x; i++)
            System.out.print(result[0][i] + " ");
        System.out.println();
        for(i=1; i<=x; i++)
            System.out.print(result[1][i] + " ");
        System.out.println("\n=======================================================================");
        for(i=1; i<=x; i++)
            System.out.print(result[0][i] + result[1][i] + - 1 + " ");
        System.out.println();
*/

        return max;
    }
    
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int x = sc.nextInt();
        if(x < 1 || x > 1000) System.exit(0);
        
        for(int i=1; i<=x; i++){
            arr[i] = sc.nextInt();
            if(arr[i] < 1 || arr[i] > 1000) System.exit(0);
        }

        System.out.printf("%d\n", getAnswer(x));
        sc.close();
    }
}

* 반례

/*
17
7 2 1 1 5 2 2 3 2 3 1 2 4 5 1 2 4 = 6

6
1 2 3 5 5 1 = 5

6
1 2 3 3 2 1 = 5

5
1 3 1 2 1 = 4

5
5 4 3 2 1 = 5

10
10 1 3 5 7 6 3 2 1 10 = 8

7
9 1 2 3 2 1 9 = 5

10
1 6 2 1 4 3 4 5 2 1 = 7

5
1 2 1 1 1 = 3

2
999 1000 = 2

10
1 2 2 2 2 2 2 2 2 2 = 2

7
1 4 3 2 1 5 6 = 5

7
1 2 4 3 2 4 1 = 6

5
1 5 4 2 3 = 4

6
3 2 1 4 5 6 = 4

7
5 1 6 2 6 2 1 = 5

9
5 1 6 2 7 3 7 2 1 = 6

10
9 8 6 2 3 5 4 10 1 7 = 6

11
1 2 3 4 5 1 5 4 3 2 1 = 9

5
5 4 3 2 3 = 4
 */