[백준] 11054 가장 긴 바이토닉 부분 수열 - DP + LIS JAVA

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

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

코드설명

DP와 LIS 문제입니다.

 

 

이전에 풀었던 11053 가장 긴 증가하는 부분수열 문제의 응용문제입니다.

 

이 문제의 핵심은,

앞에서부터 증가하는 가장 긴 증가하는 부분 수열 frontToBack_DP[] 를 구합니다.

뒤에서부터 증가하는 가장 긴 증가하는 부분 수열 BackToFront_DP[] 를 구합니다.

 

이 2개의 DP를 더한다면, 앞에서부터 가장 긴 증가하는 부분수열과 뒤에서부터 가장 긴 증가하는 부분수열을 구함으로써 해당 길이의 최대값을 구할 수 있습니다. 

 

문제예시

10
1 5 2 1 4 3 4 5 2 1

frontToBack_DP[]
1 2 2 1 3 3 4 5 2 1 

backToFront_DP[]
1 5 2 1 4 3 3 3 2 1

sum_DP[]
2 7 4 2 7 6 7 8 4 2

 

위와 같이 sum_DP[]에 바이토닉의 최대길이가 나옵니다.

SUM_DP의 최대값은 8 인데, 

앞에서부터 증가하는 부분수열과

뒤에서부터 증가하는 부분수열을 구하면서 해당 지점은 2번 더해지게 됩니다. 그러므로 -1 처리를 하여 출력합니다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.stream.Collectors;

public class Main {
	public static int N;
	public static int[] arr;
	public static int[] frontToBack_dp;
	public static int[] backToFront_dp;
	public static int[] answer_dp;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[N];
    	frontToBack_dp = new int[N];
    	backToFront_dp = new int[N];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		
    		arr[i] = Integer.parseInt(st.nextToken());
    	}

    	frontToBack_dp[0] = 1;
    	for(int i=1;i<N;i++) {
    		frontToBack_dp[i] = 1;
    		for(int j=0; j<i; j++) {
        		if(arr[i] > arr[j]) { //만약 현재값이 전값보다 크다면,
        			frontToBack_dp[i] = Math.max(frontToBack_dp[i], frontToBack_dp[j] + 1);
        		}    			
    		}
    	}
//    	for(int a : frontToBack_dp) {
//    		System.out.print(a+" ");
//    	}
//    	System.out.println();
    	
    	backToFront_dp[N-1] = 1;
    	for(int i=N-2;i>=0; i--) {
    		backToFront_dp[i] = 1;
    		for(int j=N-1; j>i; j--) {
    			if(arr[i] > arr[j] ) {
    				backToFront_dp[i] = Math.max(backToFront_dp[i], backToFront_dp[j] + 1);
    			}
    		}
    	}
//    	for(int a : backToFront_dp) {
//    		System.out.print(a+" ");
//    	}    	
//    	System.out.println();
    	
    	
    	
    	for(int i=0;i<N;i++) {
    		int sum = frontToBack_dp[i] + backToFront_dp[i];
    		answer = Math.max(answer,  sum);
    	}
    	System.out.println(answer - 1);
    }
    
    
    
    
    
    
    
}