백준 11054 가장 긴 바이토닉 부분 수열(Gold 4)

정답코드

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

public class LongestBitonicSeries {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		int [] series = new int[N];
		int [] result = new int[N];
		int [][]DP = new int[2][N];
		Arrays.fill(DP[0],1);
		Arrays.fill(DP[1],1);
		String [] in = br.readLine().split(" ");
		
		for(int i = 0; i < N; i++) {
			series[i] = Integer.parseInt(in[i]);
		}
		
        //오른쪽 방향으로 증가하는 수열 체크
		for(int i = 1; i < N; i++) {
			for(int j = 0; j<i; j++) {
				if(series[j]<series[i]&&DP[0][j]>=DP[0][i]) {
					DP[0][i] = DP[0][j]+1;
				}
			}
		}
		
        //왼쪽 방향으로 증가하는 수열 체크
		for(int i = N-2; i >= 0; i--) {
			for(int j = N-1; i<j; j--) {
				if(series[j]<series[i]&&DP[1][j]>=DP[1][i]) {
					DP[1][i] = DP[1][j]+1;
				}
			}
		}
		
        양쪽으로 순회한 증가하는 수열의 같은 idx를 더하고 -1
		for(int i = 0; i < N; i++) {
			result[i] = DP[0][i]+DP[1][i]-1;
			
		}
		
		int rs = 1;
		for(int i = 0; i < N; i++) {
			rs = Math.max(rs,result[i]);
		}
		
		System.out.println(rs);
	}

}

전략

• 바이토닉 수열은 어떤 한 숫자를 기준으로 왼쪽에서 부터 증가하는 수열, 오른쪽에서 부터 증가하는 수열의 길이를 합한 것이기 때문에 DP배열을 2개를 만들어서 각각의 방향에서 계산

• 내가 구하려는 idx까지 온다면 자기 idx는 두번 더해지기 때문에 -1을 해준다

• DP를 만드는 데는 O(N^2)*2 + result 배열 만드는 데는 O(N)으로 가능함