[11054] 가장 긴 바이토닉 부분 수열 - Java[자바]

 

 

| 문제 링크

 

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

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

 

 

 

 

---

 

 

 

 

| 문제

 

 

1. 증가하거나, 감소하거나, 증가하다 감소하는 부분 수열을 바이토닉 수열이라고 합니다.
2. 크기가 N인 수열이 주어졌을 때, 가장 긴 바이토닉 수열의 길이를 출력하시오. (1 ≤ N ≤ 1,000)

 

 

 

 

---

 

 

 

 

| 풀이

 

 

1. 증가하는 부분 수열 DP와 감소하는 부분 수열 DP를 모두 구해줍니다.
   증가하는 부분 수열: i번째 인자에 대해 0부터 i-1(j)번째 인자와 비교해 i번째 인자가 더 큰 경우 해당 j번째 DP값 +1과 i번째 DP값을 비교해 더 큰 값을 i번째 DP 값으로 설정해 줍니다.
   감소하는 부분 수열: i번째 인자에 대해 n-1부터 i+1(j)번째 인자와 비교해 i번째 인자가 더 큰 경우 해당 j번째 DP값 +1과 i번째 DP값을 비교해 더 큰 값을 i번째 DP 값으로 설정해 줍니다.
2. 두 DP의 합을 더한 DP를 만들어 가장 큰 숫자를 가진 값을 출력합니다.

 

 

 

 

---

 

 

 

 

| 코드

 

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] nums = new int[N];
		int[] inc = new int[N];
		int[] dec = new int[N];
		
		for(int i = 0; i<N; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		
		//증가하는 수열의 길이 입력
		for(int r = 0; r<N; r++) {
			inc[r] = 1;
			//왼쪽에 있는 숫자들을 탐색
			for(int l = 0; l<r; l++) {
				if(nums[r]>nums[l])
					inc[r] = Math.max(inc[l]+1, inc[r]);
			}
		}
		//감소하는 수열의 길이 입력
		for(int l = N-1; l>=0; l--) {
			dec[l] = 1;
			//왼쪽에 있는 숫자들을 탐색
			for(int r = N-1; l<r; r--) {
				if(nums[l]>nums[r])
					dec[l] = Math.max(dec[r]+1, dec[l]);
			}
		}
		//증가하는 수열의 길이와 감소하는 수열의 길이의 합이 가장 긴 인덱스가 가장 긴 바이토닉 수열
		int max = Integer.MIN_VALUE;
		for(int i = 0; i<N; i++) {
			max = Math.max(max, inc[i]+dec[i]);
		}
		//해당 인덱스의 숫자는 중복으로 들어가있어 -1
		bw.write(String.valueOf(max-1));
		br.close();
		bw.close();
		
	}
	
}