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

🔺 문제

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

바이토닉 (= 토닉이 2개)

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] seq;
    static int[] r_dp;
    static int[] l_dp;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        seq = new int[N + 1];
        r_dp = new int[N + 1];    // LIS
        l_dp = new int[N + 1];    // LDS
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 1 ; i <= N ; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
            r_dp[i] = 1;
            l_dp[i] = 1;
        }
        
        LIS();
        LDS();
        
        int max = 0;
        for(int i = 1 ; i <= N ; i++) {
            if(max < r_dp[i] + l_dp[i]) {
                max = r_dp[i] + l_dp[i];
            }
        }
        
        System.out.println(max - 1);
    }
    
    // 최장 증가 부분 수열 (L → R)
    static void LIS() {
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j < i ; j++) {  // 1 ~ i번 이전 원소 출력
                if(seq[j] < seq[i] && r_dp[i] < r_dp[j] + 1) {
                    r_dp[i] = r_dp[j] + 1;
                }
            }
        }
    }
    
    // 최장 감소 부분 수열 (R → L)
    static void LDS() {
        for(int i = N ; i >= 1 ; i--) { // 🔔 뒤에서부터 시작
            for(int j = N ; j > i ; j--) {  // 🔔 맨 뒤에서 i 이전 원소들 탐색
                if(seq[j] < seq[i] && l_dp[i] < l_dp[j] + 1) {
                    l_dp[i] = l_dp[j] + 1;
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ DP (Bottom-Up)
- 바이토닉 수열 = 양 방향으로 구한 LIS, LDS의 합 - 1 (중복 제거)
 → LIS  : 왼쪽에서 출발
 → LDS : 오른쪽에서부터 출발

 

💥 유의사항

• 감소하는 부분 수열 LDS 의 길이 ⇨ 뒤에서부터 증가하는 부분 수열의 길이 구하는 것과 동일

 

 

---

🔺 다른 풀이들

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

---

💬 느낀 점

전에 봤던 11053번: 가장 긴 증가하는 부분 수열 한 번 풀이랑 과정 다시 보고 이해가 훨씬 빨리 됐다!!!!!

 

 

1회독	2회독	3회독	4회독	5회독
V	240426

---

(참고)

✔ 풀이 참고

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