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

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

 

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

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

---

1.  아이디어

 

앞에서 뒤로 LIS를 구하고 뒤에서 앞으로 LIS를 구하면 간단하게 해결할 수 있다.

---

2. 문제풀이

 

아이디어처럼 서로 다른 방향으로 LIS를 구한 후 같은 인덱스를 비교해보면 두 LIS의 길이의 합 - 1 이(자기 자신 제외) 바이토닉 부분 수열의 길이가 되는 점을 활용해서 구현했다. 이때 뒤에서 앞으로 LIS를 구해야하고 앞에서 뒤로 LDS를 구하는 것이 아님에 주의해야했다.

---

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int max = 0;

        int[] dp1 = new int[N];
        Arrays.fill(dp1, 1);

        for (int k = 0; k < N; k++) {
            for (int i = 0; i < k; i++) {
                if (arr[i] < arr[k]) dp1[k] = Math.max(dp1[k], dp1[i] + 1);
            }
        }

        int[] dp2 = new int[N];
        Arrays.fill(dp2, 1);

        for (int k = N - 1; k >= 0; k--) {
            for (int i = N - 1; i > k; i--) {
                if (arr[i] < arr[k]) dp2[k] = Math.max(dp2[k], dp2[i] + 1);
            }
        }

        for (int i = 0; i < N; i++) {
            max = Math.max(max, dp1[i] + dp2[i] - 1);
        }

        System.out.println(max);
    }
}

---

4. 후기