[BOJ/백준] 11054. 가장 긴 바이토닉 부분 수열 (Java)

🔎문제

https://www.acmicpc.net/problem/11054#:~:text=%ED%9E%8C%ED%8A%B8,%EB%B0%94%EC%9D%B4%ED%86%A0%EB%8B%89%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4%EC%9D%B4%EB%8B%A4.

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

 

💡풀이

증가하다 감소하거나, 감소만하거나, 증가만 하는, 변곡점이 하나 이하인 수열을 구하는 문제이다.

증가하는 부분과 감소하는 부분이 각각 길수록 바이토닉 수열도 길것이다.

 

그러므로 LIS 알고리즘(?) 을 이용해 앞에서부터는 가장 긴 증가하는 부분 수열을 구하고, 뒤에서부터는 가장 긴 증가하는 부분 수열을 구한다. 뒤에서부터 가장 긴 증가하는 부분 수열은 앞에서부터 구한 가장 긴 감소하는 부분 수열과 같겠다. 아직 LIS를 풀지 않았다면 먼저 풀고 오는것을 추천한다. 생각보다 유용하다.

 

이때 어떤 지점에서 바이토닉 부분 수열이 가장 긴지 구하면 된다.

 

N의 크기는 최대 1000 이므로, DP로 구해도 괜찮다.

 

 

1

5

2

1

4

3

4

5

2

1

이런 수열이 주어질때, 가장 긴 바이토닉 부분 수열은 {1 5 2 1 4 3 4 5 2 1} 이다.

 

 

앞에서부터 가장 긴 증가하는 부분 수열 DP배열

i	0	1	2	3	4	5	6	7	8	9
dp[i]	1	2	2	1	3	3	4	5	2	1

가장 긴 증가하는 부분 수열은 1 5 2 1 4 3 4 5 2 1 이다.

 

뒤에서부터 가장 긴 증가하는 부분 수열 DP2배열 = 가장 긴 감소하는 부분 수열

i	0	1	2	3	4	5	6	7	8	9
dp2[i]	1	5	2	1	4	3	3	3	2	1

뒤에서부터 가장 긴 증가하는 부분 수열은1 5 2 1 4 3 4 5 2 1 이다.

 

i는 0부터, 끝까지 증가시키며 어느 지점에서 dp[i] + dp2[i] 가 최대인지 구해보자.

i	0	1	2	3	4	5	6	7	8	9
dp[i] + dp2[i]	2	7	4	2	7	6	7	8	4	2

i가 7일때가 8로, 최대이다.

i가 7일때, 앞부분은 1, 2, 3, 4, 5(i = 7) 이고, 뒷부분은 5(i = 7), 2, 1이다.

5가 두번 세어졌으므로 하나를 뺀 7이 답이다.

 

📃소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {

    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        int[] dp = new int[n];
        int[] dp2 = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(dp2, 1);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    dp2[i] = Math.max(dp2[i], dp2[j] + 1);
                }
            }
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i] + dp2[i]);
        }

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