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

문제

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

 

접근 방식

바이토닉 수열인 오름차순, 내림차순, 오름차순 + 내림차순 수열 중 가장 긴 것을 찾아야 한다.

 

이전에 풀었던 문제 중 가장 긴 증가하는 부분 수열을 응용하면 풀 수 있는 문제인데

v		v			v	v	v
1	5	2	1	4	3	4	5	2	1

 

만약에 위와 같은 수열이 있다면 1, 2, 3, 4, 5가 가장 긴 증가하는 부분 수열일 것이고

	v			v	v			v	v
1	5	2	1	4	3	4	5	2	1

 

가장 긴 감소하는 부분 수열은 위와 같을 것이다.

 

가장 긴 증가하는 부분 수열과 감소하는 부분 수열의 길이를 표로 정리하면 다음과 같다.

1	5	2	1	4	3	4	5	2	1

1	2	2	1	3	3	4	5	2	1
1	5	2	1	4	3	3	3	2	1

 

이렇게 표를 정리하고 나면 같은 값에 해당하는 길이끼리 합치면

오름차순과 내림차순이 합쳐진 바이토닉 부분 수열을 만들 수 있는 것을 알 수 있다.

 

예를 들어 길이가 5인 증가하는 부분 수열과 3인 감소하는 부분 수열을 합치면

1, 2, 3, 4, 5 + 5, 2, 1 = 1, 2, 3, 4, 5, 5, 2, 1 만들어질 것이고

5는 겹치는 부분이니 총개수의 합인 8에서 1을 빼주면 된다.

 

정리하면 두 경우의 부분 수열의 길이를 구해서 합한 후에 가장 큰 값을 구해주면 된다.

 

풀이

public class Main {

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

		int n = Integer.parseInt(br.readLine());
		int max = 0;
		int[] arr = new int[n];
		int[] dp = new int[n];
		int[] dpr = new int[n];

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

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

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

		for (int i = n - 1; i >= 0; i--) {
			dpr[i] = 1;

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

			dp[i] += (dpr[i] - 1);
			max = Math.max(dp[i], max);
		}

		System.out.println(max);
	}
}