[백준_11054번] 가장 긴 바이토닉 부분 수열

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

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

[문제]

 수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다. 수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

 

[코드]

import java.util.*;

/*
 * 알고리즘
 * 왼쪽에서 오른쪽으로 진행하는 부분수열과 오른쪽에서 왼쪽으로 진행하는 부분수열을 합쳐
 * 오름차순과 내림차순이 합쳐진 수열을 완성한다. 
 * 이때 결과 값은 원소 1개씩이 중복되어 있기 때문에 -1을 해줘야 한다.
 */
public class BaekJoon_11054 {
	public static int n;
	public static int[] num;
	public static int[] r_dp;
	public static int[] l_dp;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		num=new int[n];
		r_dp=new int[n];
		l_dp=new int[n];
		
		for(int i=0;i<n;i++)
			num[i]=sc.nextInt();
		
		LIS(); LDS();
		
		int max=0;
		for(int i=0;i<n;i++) {
			if(max<l_dp[i]+r_dp[i])
				max=l_dp[i]+r_dp[i];
		}
		
		System.out.println(max-1);
	}
	
	// 왼쪽에서 오른쪽으로 진행하는 부분수열 찾기
	public static void LIS() {
		for(int i=0;i<n;i++) {
			l_dp[i]=1; // 자신을 포함한 최소한의 수열 1로 초기화
			
			// 이전 원소들 탐색
			for(int j=0;j<i;j++) {
				// 자신보다 이전의 원소가 작으면서 i번째 dp가 j번째 dp+1 값보다 작은 경우
				if(num[i]>num[j]&&l_dp[i]<l_dp[j]+1)
					l_dp[i]=l_dp[j]+1;
			}
		}
	}
	
	// 오른쪽에서 왼쪽으로 진행하는 부분수열 찾기
	public static void LDS() {
		// 맨 뒤부터 시작
		for(int i=n-1;i>=0;i--) {
			r_dp[i]=1; // 자신을 포함한 최소한의 수열 1로 초기화
			
			// 이전 원소들 탐색
			for(int j=n-1;j>i;j--) {
				// 자신보다 이전의 원소가 작으면서 i번째 dp가 j번째 dp+1 값보다 작은 경우
				if(num[i]>num[j]&&r_dp[i]<r_dp[j]+1)
					r_dp[i]=r_dp[j]+1;
			}
		}
	}
}

 

[고찰]

 이번 문제는 백준 11053 문제에서 확장된 문제이다. 하지만 어떻게 풀어야 하는지 알고리즘이 떠오르지 않아 다른 사람들의 풀이를 보며 힌트를 얻었다. 

 결론은 앞에서 부터 시작하는 부분 수열과 뒤에서 부터 시작하는 부분 수열을 합하는 것이었다. 이때 결과 값은 단순히 배열 값을 더한 것이기 때문에 중복되는 원소 1개씩을 빼줘야 한다. 이를 구현하는 것은 앞선 문제를 풀어봤기 때문에 쉽게 해결할 수 있었지만 알고리즘을 떠올리는 것은 어려웠던 문제이다.