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

👉 문제링크

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

---

---

🔸 문제 분석 🔸

• 중간 원소를 기준으로 오름차순 후 내림차순이 이어지는 수열을 바이토닉 수열이라고 한다.
• 주어지는 수열의 부분 수열 중 가장 긴 바이토닉 수열의 길이를 출력한다.

🔸 문제 풀이 🔸

• 각 인덱스 별로 가장 긴 오름차순 수열과 가장 긴 내림차순 수열의 길이를 따로 구해 저장한다.
• 같은 인덱스의 두 값의 합 중 최대값을 출력한다.

🔸 코드 🔸

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

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

        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        int[] up = new int[N];
        int[] down = new int[N];

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

        // 가장 긴 증가하는 부분 수열
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (A[i] > A[j])
                    up[i] = Math.max(up[i], up[j] + 1);
            }
        }
        // 가장 긴 감소하는 부분 수열
        for (int i = N - 1; i >= 0; i--) {
            for (int j = i + 1; j < N; j++) {
                if (A[i] > A[j])
                    down[i] = Math.max(down[i], down[j] + 1);
            }
        }

        int max = 0;
        for (int i = 0; i < N; i++) {
            max = Math.max(max, up[i] + down[i]);
        }

        bw.write(Integer.toString(max + 1));
        bw.flush();
    }

}

🔸 코드 해석 🔸

• 주어진 수열을 int형 배열 A에 저장 후 앞에서 뒤로 오름차순, 뒤에서 앞으로 내림차순 수열의 크기를 저장해 간다.
  • 점화식은 max(현재 인덱스 값, 지나온 인덱스들의 최대값 +1) 이다.
  • 여기서 지나온 인덱스의 A배열 값이 현재 인덱스의 A배열 값보다 작아야 한다.
• 이렇게 구해진 up, down int형 배열들을 같은 인덱스끼리 더해서 최대값+1을 출력한다.
  • +1을 하는 이유는 현재 인덱스의 원소가 포함되지 않은 값이기 때문이다.

---

🔸 end 🔸

• 처음엔 N이 1000으로 작은 것 같아서 브루트 포스로 풀려고 했지만, 부분 수열의 모든 경우의 수를 DFS로 계산했더니 시간초과가 났다.
• 가장 긴 오름차순 부분 수열과 가장 긴 내림차순 부분 수열의 합이라는 힌트를 보고 풀어낼 수 있었다.