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

 

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

이 문제를 풀기전에 먼저 '가장 긴 증가하는 부분 수열' 문제를 풀기를 권장한다! 왜냐하면 해당 문제를 응용해서 푸는 문제이기 때문이다. 

 

S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN

이렇게 생긴 수열을 바이토닉 수열이라고 한다. 

여기서 보이는 규칙은 Sk 값을 기준으로 왼쪽은 '증가하는 부분 수열' 이고 오른쪽은 '감소하는 부분 수열' 이라는 점이다.

그렇다! Sk 값의 가장 긴 바이토닉 부분 수열은 결국

0부터 Sk까지의  가장 긴 증가하는 부분 수열 + Sk부터 Sn까지의 가장 긴 감소하는 부분 수열 -1 이다 

(여기서 -1은 Sk값이 두번 겹치기 때문에 해줘야한다.)

 

그러면 일단 배열을 세개 만들어준다. 첫번째는 각 Si 값들의 가장 긴 증가하는 부분 수열 길이 저장

두번째는 각 Si 값들의 가장 긴 감소하는 부분 수열 길이 저장,

그리고 세번째는 이 두개를 합친 각 Si 값들의 가장 긴 바이토닉 부분 수열 길이를 저장해준다.

 

그러면 첫번째로 0부터 k 값까지의 가장 긴 증가하는 부분 수열을 구해주는 소스를 보자 (여기서 k는 0부터 n-1까지이다)

for(int i=0; i<n; i++) {
	inc[i]=1;
	for(int j = 0; j<i;j++) {
		if(arr[i]>arr[j] && inc[j]+1>inc[i]) inc[i]=inc[j]+1;
	}
}

소스를 통해 알 수 있듯 왼쪽 - 오른쪽의 가장 긴 증가하는 부분 수열값을 inc 배열에 저장해주고 있다. 

 

두번째로 k 값부터 n 까지의 가장 긴 감소하는 부분 수열을 구해주는 소스이다.(여기서 k는 n-1부터 0까지이다)

for(int i = n-1; i>=0; i--) {
	dec[i]=1;
	for(int j =i+1; j<n; j++) {
		if(arr[j]<arr[i]&&dec[j]+1>dec[i]) dec[i]=dec[j]+1;
		}
}

 

그리고 이 두 루프를 한 루프로 합친 소스이다. (but 루프를 두개로 나누어도 상관없다. 시간복잡도는 어차피 O(n^2)으로 같기 때문이다.

for(int i=0; i<n; i++) {
	inc[i]=1;
	dec[n-i-1]=1;
	for(int j = 0; j<i;j++) {
		if(arr[i]>arr[j] && inc[j]+1>inc[i]) inc[i]=inc[j]+1;
		if(arr[n-i-1]>arr[n-j-1]&& dec[n-j-1]+1>dec[n-i-1]) dec[n-i-1]=dec[n-j-1]+1;
	}
}

 

 

그러면 아래는 전체 자바 소스이다.

import java.util.*;
import java.io.*;

public class Main {	
	private static int [] arr;
	private static int[]dec;
	private static int[]inc;
	private static int[]res;
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk= new StringTokenizer(br.readLine());
		int n = Integer.parseInt(stk.nextToken()); //수열 길이 
		arr = new int[n];
		dec = new int[n]; //감소 
		inc = new int[n]; //증가
		res = new int[n];
		String[] s;
		s = br.readLine().split(" ");
		for(int i=0; i< n;i++) {
			arr[i]=Integer.parseInt(s[i]);
		}
		for(int i=0; i<n; i++) {
			inc[i]=1;
			dec[n-i-1]=1;
			for(int j = 0; j<i;j++) {
				if(arr[i]>arr[j] && inc[j]+1>inc[i]) inc[i]=inc[j]+1;
				if(arr[n-i-1]>arr[n-j-1]&& dec[n-j-1]+1>dec[n-i-1]) dec[n-i-1]=dec[n-j-1]+1;
			}
		}
		int max=0;
		for(int i=0; i<n; i++) {
			res[i]=inc[i]+dec[i]-1;
			if(max<res[i]) max=res[i];
		}
		System.out.println(max);
		
	}
}