[BOJ - JAVA] 11054 - 가장 긴 바이토닉 부분 수열(LIS, LDS, DP)

# 주소

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

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

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    public static Integer[] r_dp;
    public static Integer[] l_dp;
    public static int[] arr;
    
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        
        r_dp = new Integer[n];
        l_dp = new Integer[n];
        arr = new int[n];
        
        for(int i = 0; i < n; i++){
            arr[i] = scan.nextInt();
        }
        
        for(int i = 0; i < n; i++){
            lis(i);
            lds(i);
        }
        int max = -1;
        for(int i = 0; i < n; i++){
            max = Math.max(r_dp[i] + l_dp[i], max);
        }
        System.out.println(max - 1);
    }
    public static int lis(int n){
        if(r_dp[n] == null){
            r_dp[n] = 1;
            
            for(int i = n-1; i >= 0; i--){
                if(arr[i] < arr[n]){
                    r_dp[n]  = Math.max(r_dp[n], lis(i) + 1);
                }
            }
        }
        return r_dp[n];
        
    }
    public static int lds(int n){
        if(l_dp[n] == null){
            l_dp[n] = 1;
            for(int i = n+1; i < l_dp.length; i++){
                if(arr[i] < arr[n]){
                    l_dp[n] = Math.max(l_dp[n], lds(i) + 1);
                }
            }
        }
        return l_dp[n];
    }
    
}

LIS(가장 긴 증가하는 부분 수열)와 LDS(가장 긴 감소하는 부분 수열)을 가장 잘 이해할 수 있는 문제가 아닐까 싶습니다.

바이토닉 수열이란 문제에서도 나와있듯이 수가 증가하다가 감소할 때 그 개수가 가장 많은 것을 출력하도록 유도하고 있는데요.

이 문제는 재귀함수를 기본적으로 사용하면서 탐색을 빠르게 하기 위해 메모이제이션을 이용했습니다.

메모이제이션이란 탐색을 빠르게 하기 위해 C언어에서 사용하는 포인터처럼 자료의 값을 찾는 것이 아닌 인덱스를 탐색하여 함수에 값이 들어있지 않을 때(arr[i] == null) 사용하기 편합니다.(기존의 int 형태라면 arr[i] == 0일 때 탐색 가능하지만 시간이 많이 걸린다는 단점이 있음)

그리고 LIS함수를 잘 보시면 탐색하지 않은 dp값에 대해서는 1을 가집니다.

그리고 arr[n]보다 작은 arr[i]에 대해서 arr[i]는 n에서 부터 시작하여 인덱스의 왼쪽 방향으로 향할 때 r_dp[n]과 lis(i)의 값에 +1을 한 값을 비교합니다. 그럼 당연히 i가 1이상일 때 부터는 (저 예제에서) lis(i)+1한 값이 더 클 것이고 결론적으로 증가하는 부분 수열일때는 항상 lis(i) + 1이 담기게 됩니다.

그럼 만약 1 2 3 4 3 5 이렇게 담겨 있으면 어떻게 될까요? 우리는 여기서 lis 는 1 2 3 4 5인 걸 알 수 있죠??

여기서 r_dp의 값은 그럶 어떻게 될까요? i가 6일 때 생각해 봅시다 i가 6이라면 arr[i] < arr[6]일 때 r_dp[6] = Math.max(r_dp[i], lis(i) + 1)입니다. 그리고 r_dp[i] 의 값은 i가 4일 때 4이고 i가 5일 때는 3입니다. 따라서 r_dp[6]에 담기는 값은 r_dp[4]가 4였으므로 lis(4)역시 4이고 거기에 +1된 값인 5가 최종적으로 저장되는 것입니다.

 

그렇다면 LDS는 어떻게 구할까요?? 이는 기준점 n에서 인덱스의 오른쪽 방향으로 배열 끝까지 부호를 바꾸어서 생각해주시면 되겠습니다. 그럼 최종적으로 l_dp값이 나올텐데 이 때 정답을 출력하기 위해서는 당연히 이것들의 값을 각 인덱스마다 더한 값을 찾습니다. 그리고 인덱스가 한 개 겹치므로 최종적으로 더해진 값에서 1을 빼주면 그것이 답이되겠습니다.

예) 1 2 3 5 2 1

    1 3 2 3 2 1 이면 두 개 더했을 때 8이 되고 여기서 -1해주어 7이 나오는 것이 정상