알고리즘 풀이 - 백준 11054(가장 긴 바이토닉 부분 수열 ,DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조
LIS 관련 포스팅은 여기를 참조
관련 문제인 11053번(가장 긴 증가하는 부분 수열) 포스팅은 여기를 참조
관련 문제인 14002번(가장 긴 증가하는 부분 수열 4) 포스팅은 여기를 참조
관련 문제인 11055번(가장 큰 증가 부분 수열) 포스팅은 여기를 참조
관련 문제인 11722번(가장 긴 감소 하는 부분 수열) 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

 

이 문제는 가장 긴 바이토닉 부분 수열을 구하는 문제이다.

 

 

2. 풀이

 

바이토닉의 정의부터 알아보자.

바이토닉 수열은 수열에서 특정 위치의 하나의 값을 기준으로 왼쪽으로는 증가, 오른쪽으로는 감소하는 수열을 이루는 형태를 의미한다.

즉, 1, 2, 3, 2, 1과 같이 수열이 이루어졌다면 3을 기준으로 좌측은 증가, 우측은 감소하니 바이토닉 수열이라고 볼 수 있게 된다.

 

이 문제는 LIS / LDS 문제를 다 포함해서 활용할 수 있는지를 묻는 문제라고도 볼 수 있다. 바이토닉 부분 수열을 구하려면 다음과 같이 구해야 한다.

① 좌측에서 부터 시작하여 해당 값을 끝으로 하는 가장 긴 증가하는 부분 수열을 구한다.
② 좌측에서 부터 시작하여 해당 값을 시작으로 하는 가장 긴 감소하는 부분 수열을 구한다.

 

위에서 ①은 단순히 LIS를 구하는 문제와 동일하다. 그런데 ②는 단순히 LDS 문제와는 다르다. 왜냐하면 각 위치에서 끝나는 것이 아니라 각 위치에서 시작하는 것으로 정의되기 때문이다.

그런데 잘 생각해보면, 해당 값에서 시작하여 감소하므로 역으로 생각하면 우측에서 부터 시작해 해당 값을 끝으로 하는 가장 긴 증가하는 부분 수열과 같다고 볼 수 있다.

 

예를 들어서 수열이 3, 2, 1 이라고 해보자. 3에서 시작하는 가장 긴 감소하는 부분 수열이나, 우측의 1에서 시작하여 3을 끝으로 하는 가장 긴 증가하는 부분 수열이나 동일하다!

즉, 이 문제는 LIS를 구하되 좌측에서 부터 시작하는 것과 우측에서 부터 시작하는 것을 각각 구해서 그 결과값을 더하면 정답이 나온다.

 

간단히 문제의 정의, 기저 상태, 점화식을 알아보자.
정의 : 길이 N의 배열에서 바이토닉 부분 수열 길이 구하기

기저 상태는 좌측 기준 LIS는 index가 0일 때이며, 우측 기준 LIS는 index가 n-1일 때이다. 각각의 배열을 lis, lis2라고 생각하면 다음과 같다.
기저 상태 : lis[0] = 1, lis2[n-1] = 1

 

점화식은 다음과 같다. 원 배열을 arr 배열이라고 가정하자.
점화식 ▼
좌측 기준의 LIS 의 경우 : lis[i] = lis[j] + 1(단, j < i and arr[j] < arr[i])
우측 기준의 LIS 의 경우 : lis2[i] = lis2[j] + 1(단, j > i and arr[j] < arr[i])

 

각각을 구했으면 마지막 정답은 어떻게 구할까?
정답 : MAX(lis[i] + lis2[i]) - 1
-1을 해주는 이유는 i번째의 숫자가 2번 중복되기 때문이다.

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[] arr;
    static int[] left;
    static int[] right;
    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());
        arr = new int[n];
        left = new int[n];
        right = new int[n];
        
        String line[] = br.readLine().split(" ");
        
        // 우선 원 배열 저장하며 좌측부터의 LIS를 구함
        for(int i=0; i < n; i++){
            arr[i] = Integer.parseInt(line[i]);
            left[i] = 1;
            for(int j=i-1; j >= 0; j--){
                if(arr[j] < arr[i] && left[i] <= left[j]){
                    left[i] = left[j] + 1;
                }
            }
        }
        
        // 우측 부터의 LIS도 구하자
        for(int i=n-1; i >= 0; i--){
            right[i] = 1;
            for(int j=i+1; j < n; j++){
                if(arr[j] < arr[i] && right[i] <= right[j]){
                    right[i] = right[j] + 1;
                }
            }
        }
        
        // 그럼 좌 / 우측의 각각의 값을 더해서 -1을 한 값 중 최대값을 구한다.
        // -1을 하는 이유는 해당 위치가 2번 중복 되기 때문임
        int result = 0;
        for(int i=0; i < n; i++){
            result = Math.max(result, left[i] + right[i] - 1);
        }
        
        bw.write(String.valueOf(result));
        br.close();
        bw.flush();
    }
}

 

2) Top-Down 방식

import java.io.*;
public class Main{
    static int[] arr;
    static int[] left;
    static int[] right;
    static int n;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        left = new int[n];
        right = new int[n];
        
        String line[] = br.readLine().split(" ");
        
        for(int i=0; i < n; i++){
            arr[i] = Integer.parseInt(line[i]);
        }
        
        // 좌측에서의 가장 긴 증가하는 수열을 우선 구하자.
        lis(n-1);
        
        // 우측에서 시작하는 가장 긴 증가하는 수열을 구하자
        lis2(0);
        
        int result = 0;
        for(int i=0; i < n; i++){
            result = Math.max(result, left[i] + right[i] - 1);
        }
        
        bw.write(String.valueOf(result));
        br.close();
        bw.flush();
    }
    
    // Top-Down 방식의 좌측 LIS
    public static int lis(int k){
        // 기저상태 또는 이미 이전의 값이 있는 경우
        if(k == 0) return left[k] = 1; 
        if(left[k] > 0) return left[k];
        
        left[k] = 1; // 우선 1로 초기화
        for(int i=k-1; i >= 0; i--){
            int temp = lis(i);
            if(arr[i] < arr[k] && left[k] <= temp){
                left[k] = temp + 1;
            }
        }
        return left[k];
    }
    
    // Top-Down 방식의 우측 LIS
    public static int lis2(int k){
        // 기저상태 또는 이미 이전의 값이 있는 경우
        if(k == n-1) return right[k] = 1;
        if(right[k] > 0) return right[k];
        
        right[k] = 1; // 우선 1로 초기화
        // 자신보다 이전의 값들과 비교해야함. 그 중 가장 큰 값으로!
        for(int i=k+1; i < n; i++){
            int temp = lis2(i);
            if(arr[i] < arr[k] && right[k] <= temp){
                right[k] = temp + 1;
            }
        }
        return right[k];
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.