[BackJoon]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)

 

출력

 

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

풀이

 

아이디어는 간단하다.

 

주어진 수열을 정방향으로 한 번, 역방향으로 한 번 탐색하며 각 자리에서의 가장 긴 증가하는 수열을 구한 뒤에

 

둘을 합친뒤 가장 큰 값을 리턴하면 된다.

 

그러나 어제 맵을 이용했던 풀이를 응용해서 풀었으나 n^2의 시간복잡도 덕분에 시간초과가 났다.

 

어떻게든 써먹어보려고 끙끙대다 아무래도 시간복잡도를 해결할 길이 없어 원래 방식으로 돌아옴.

 

위에 적은 대로 정방향과 역방향으로 배열을 순회하며 해당 자리의 LIS를 탐색 후 더했다.

 

처음에 배열을 1로 초기화 시킬 때, 검색하다가 Arrays.fill()이라는 메서드를 발견해서 사용했는데

 

상당히 유용했다. 이 글은 위 메서드를 기억하기 위한 것.

 

코드는 간단하다.

package BackJoon;

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

public class Prob11054_3 {

	static int[] increase;
	static int[] decrease;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		increase = new int[n];
		decrease = new int[n];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.fill(increase, 1);
		Arrays.fill(decrease, 1);

		for (int i = 1; i < n; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[j] < arr[i]) {
					increase[i] = Math.max(increase[i], increase[j] + 1);
				}
			}
		}

		for (int i = n - 2; i >= 0; i--) {
			for (int j = n - 1; j > i; j--) {
				if (arr[j] < arr[i]) {
					decrease[i] = Math.max(decrease[i], decrease[j] + 1);
				}
			}
		}

		int max = 0;

		for (int i = 0; i < n; i++) {
			max = Math.max(max, increase[i] + decrease[i] - 1);
		}

		System.out.println(max);
	}
}