[TIL] 99클럽 코테 스터디 32일차 TIL + 백준 11054 가장 긴 바이토닉 부분 수열

문제 풀이

 

 

문제 탐색하기

바이토닉 수열이란 수열이 값이 증가했다가 감소하는 수열을 뜻합니다. 

예제를 통해서 확인해 보자면 아래와 같습니다.

{1, 5, 2, 1, 4, 3, 4, 5, 2, 1}
--> 가장 긴 바이토닉 수열 {1, 2, 3, 4, 5, 2, 1}

 

이렇게 증가했다가 감소하는 최장 길이의 수열을 구해야합니다.

바이토닉 수열을 구하기 위해서는 LIS (최장 증가 수열) 과 LDS (최장 감소 수열)을 조합해서 구할 수 있습니다. 

 

최장 증가 수열과 최장 감소 수열의 dp 배열을 구한 뒤 해당 배열의 값을 합치면 오름차순과 내림차순이 합쳐진 수열이 완성되는데 여기서 단순히 두 수열을 합치면 원소가 1개씩 중복되기 때문에 최종 값은 -1을 해줘야합니다. 

 

{1, 5, 2, 1, 4, 3, 4, 5, 2, 1}
--> 오름차순 DP 배열 {1, 2, 2, 1, 3, 3, 4, 5, 2, 1}
--> 내림차순 DP 배열 {1, 5, 2, 1, 4, 3, 3, 3, 2, 1}
--> 두 수열의 합 배열 {2, 7, 4, 2, 7, 6, 7, 8, 4, 2}
--> -1 한 최종 배열 {1, 6, 3, 1, 6, 5, 6, 7, 3, 1}

 

최장 길이 바이토닉 수열의 길이를 구해야하기 때문에 그 값은 최종 배열의 최대값인 7이 될 것 입니다.

 

LIS (최장 증가 부분 수열) 을 통해서 문제를 푸는 방식은 아래의 게시글에 관련 문제 풀이와 함께 정리되어 있습니다.

https://coding-babo.tistory.com/177

[TIL] 99클럽 코테 스터디 31일차 TIL + 백준 2631 줄세우기

 

LDS (최장 감소 부분 수열) 은 LIS를 하는 방식에서 반대로 생각해주면 됩니다. 오른쪽에서 왼쪽으로 진행하는 오름차순 부분수열이라고 생각하면 됩니다.

 

문제 풀이

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

public class Main {

    static int[] arr;
    static int[] l_dp;
    static int[] r_dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        l_dp = new int[N];
        r_dp = new int[N];

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

        LIS(N);
        LDS(N);

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

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

    private static void LIS(int N){
        l_dp[0] = 1;

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

    private static void LDS(int N){
        r_dp[N-1] = 1;

        for(int i=N-2; i>=0; i--){
            r_dp[i] = 1;
            for(int j=N-1; j>i; j--){
                if(arr[i] > arr[j]){
                    r_dp[i] = Math.max(r_dp[i], r_dp[j]+1);
                }
            }
        }
    }
}

 

오늘의 회고

LIS와 LDS를 합쳐서 풀 수 있는 바이토닉 수열이라는 것이 있다니.. 놀랐습니다. 바이토닉 수열에 대해 알아갈 수 있는 좋은 시간이었습니다.