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

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

 

 

아직 리뷰를 쓰진 않았지만 가장 긴 증가하는 부분 수열 LIS(Longest Increasing Subsequence)을 구하는 문제를 해결했었다.

 

이번 문제는 가장 긴 바이토닉 부분 수열의 길이를 구하는 것으로, 문제에 주어진 '바이토닉 부분 수열'이란 

i) 계속 증가하는 부분 수열

ii) 증가하다가 특정 고점을 기준으로 감소하는 부분 수열

iii) 계속 감소하는 부분 수열

위 세 경우를 모두 포함한다.

 

이전에 Top-Down 방식으로 해결한 LIS 문제의 경우 주어진 배열 A에서 반환받고자 하는 특정 요소(N)에서의 가장 긴 증가하는 부분 수열의 길이는 A[N]이 A[N-1]보다 크다면 A[N-1]의 LIS값(=dp[N-1])에 1을 더해주고, 이와 같은 논리로 A[N-2], A[N-3], ... A[0] 까지 탐색을 해주며 LIS 값을 찾았다. 

 

바이토닉 문제가 이전의 LIS문제와 갖는 차이점은 '증가하는' 부분 수열 외에도 '감소하는 부분수열'과 '증가하다가 감소하는 부분수열'을 포함하는 개념이라는 것이다.

 

LIS에 적용한 방식을 적용하여 가장 긴 감소하는 부분 수열의 길이를 찾는 메소드를 추가해주고 A[0] 부터 A[N-1] 까지 증가하다가 감소하는 부분수열을 탐색하며 부분수열의 최대 값을 저장하고 출력하면 된다.

 

// 가장 긴 증가하는 부분수열의 길이를 반환하는 메소드
static int LIS (int N) {
        
    if (dpL[N] == null) {

        dpL[N] = 1;
        int idx = N-1;
		
        // A[N]의 이전 요소들 중 A[N]보다 값이 작은 요소인 경우 해당 최대 길이에 +1 한 값을 dpL[N]과 비교, 최신화 한다.
        while (idx >= 0) {
            if (A[idx] < A[N]) dpL[N] = Math.max(dpL[N], LIS(idx) + 1);
            idx--;
        }
    }

    return dpL[N];
}


// 가장 긴 감소하는 부분수열의 길이를 반환하는 메소드
static int LDS (int N) {

    if (dpR[N] == null) {

        dpR[N] = 1;
        int idx = N+1;
        
        // A[N]의 다음 요소들 중 A[N]보다 값이 작은 요소인 경우 해당 최대 길이에 +1 한 값을 dpR[N]과 비교, 최신화 한다.
        while (idx < A.length) {
            if (A[idx] < A[N]) dpR[N] = Math.max(dpR[N], LDS(idx) + 1);
            idx++;
        }
    }

    return dpR[N];
}

 

// 증가하다가 감소하는 부분수열의 길이를 구하는데 LIS와 LDS에서 현재 요소인 N은 두 번 카운팅 되므로
// LIS + LDS 값에 1을 빼준다.

int max = 0;
        
for (int i=0; i<N; i++) max = Math.max(max, LIS(i)+LDS(i)-1);

 

 

 

 

전체 코드

import java.util.*;

public class Main {
    
    static int[] A;
    static Integer[] dpL; // 왼쪽부터 i번째 까지 증가하는 가장 긴 수열의 길이 저장
    static Integer[] dpR; // i번째 부터 마지막 요소까지 감소하는 가장 긴 수열의 길이 저장
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        StringTokenizer st = null;
        
        int N = Integer.parseInt(sc.nextLine());
        
        A = new int[N];
        dpL = new Integer[N];
        dpR = new Integer[N];
        
        st = new StringTokenizer(sc.nextLine(), " ");
        
        for (int i=0; i<N; i++) A[i] = Integer.parseInt(st.nextToken());
        
        int max = 0;
        
        for (int i=0; i<N; i++) max = Math.max(max, LIS(i)+LDS(i)-1);
        
        System.out.println(max);
        
        sc.close();
    }
    
    static int LIS (int N) {
        
        if (dpL[N] == null) {
            
            dpL[N] = 1;
            int idx = N-1;
            
            while (idx >= 0) {
                if (A[idx] < A[N]) dpL[N] = Math.max(dpL[N], LIS(idx) + 1);
                idx--;
            }
        }
        
        return dpL[N];
    }
    
    static int LDS (int N) {
        
        if (dpR[N] == null) {
            
            dpR[N] = 1;
            int idx = N+1;
            
            while (idx < A.length) {
                if (A[idx] < A[N]) dpR[N] = Math.max(dpR[N], LDS(idx) + 1);
                idx++;
            }
        }
        
        return dpR[N];
    }
}