백준 11054 가장 긴 바이토닉 부분 수열 (JAVA 자바 풀이)

백준 11054 가장 긴 바이토닉 부분 수열 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

 

 

⚔ 입력

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

 

 

📣 출력

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

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

오른쪽 lis와 왼쪽 lis를 구하면 되는 문제이다. 

 

 

 

 

💡 코드 구현

 

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bufferedReader.readLine());

		int[] dpAsc = new int[1001];
		int[] dpDsc = new int[1001];
		int[] numbers = new int[1001];
		StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
		for (int i = 1; i <= N; i++) {
			int number = Integer.parseInt(stringTokenizer.nextToken());
			numbers[i] = number;
			dpAsc[i] = 1;
			dpDsc[i] = 1;
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= i; j++) {
				if (numbers[j] < numbers[i] && dpAsc[i] < dpAsc[j] + 1) {
					dpAsc[i] = dpAsc[j] + 1;

				}
			}
		}

		for (int i = N; i >= 1; i--) {
			for (int j = N; j >= i; j--) {
				if (numbers[j] < numbers[i] && dpDsc[i] < dpDsc[j] + 1) {
					dpDsc[i] = dpDsc[j] + 1;
				}
			}
		}

		int max =0;
		for (int i =0; i<=N;i++){
			if (max < dpAsc[i] + dpDsc[i]){
				max  = dpAsc[i] + dpDsc[i];
			}
		}

		System.out.println(max-1);	// 중복된 한 index를 빼주기 위해 -1
	}

}