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

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int ans = 0;
		int n = sc.nextInt();
		int S[] = new int[n];
		int up[] = new int[n];
		int down[] = new int[n];

		for (int i = 0; i < n; i++) {
			S[i] = sc.nextInt();
		}

		// 상승
		for (int i = 0; i < n; i++) {
			int max = 0;
			for (int j = 0; j < i; j++) {
				if (S[j] < S[i]) {
					max = Math.max(max, up[j]);
				}
			}
			up[i] = max + 1;
		}

		// 하강
		for (int i = n-1; i >= 0; i--) {
			int max = 0;
			for (int j = n-1; j > i; j--) {
				if (S[j] < S[i]) {
					max = Math.max(max, down[j]);
				}
			}
			down[i] = max + 1;
		}

		for (int i = 0; i < n; i++) {
			ans = Math.max(ans, up[i]+down[i]);
		}
		
		System.out.println(ans-1);
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

 

인덱스 0부터 n-1까지 가장 긴 증가하는 부분 수열의 길이를 up배열에 저장해놓습니다.
up[i] : 0에서 i까지 중에서 가장 긴 증가 부분 수열의 길이

 

반대로 인덱스 n-1부터 0까지 거꾸로 봤을 때 가장 긴 증가하는 부분 수열의 길이를 down배열에 저장해놓습니다.
down[i] : n-1에서 i까지 중에서 가장 긴 증가 부분 수열의 길이
다른 말로,
down[i] : i에서 n-1까지 중에서 가장 긴 감소 부분 수열의 길이

 

알고리즘의 핵심은

x번째를 볼 때 (0~x)에서 가장 긴 증가 부분 수열의 길이 + (x~n-1)에서 가장 긴 감소 부분 수열의 길이 을 안다면

0~n-1에서 가장 긴 바이토닉 수열을 알아낼 수 있습니다.

 

바이토닉 수열은 '산' 모양을 띄게 되는데 예를 들어 S[5]가 산꼭대기라고 가정하고 바이토닉 수열의 길이를 찾으면

바이토닉 수열의 길이 = 0~5에서 가장 긴 증가 부분 수열의 길이 + 5~9에서 가장 긴 감소 부분 수열의 길이
ans = up[5]+down[5] 이고 여기서 5가 중복으로 들어갔으므로 -1을 해주어 ans값을 출력해주면 됩니다.

 

🔗 링크

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

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