[PS] 백준 가장 긴 바이토닉 부분 수열 java 풀이

11054번: 가장 긴 바이토닉 부분 수열 (acmicpc.net)

처음 문제 접근

• DP 같이 생겼다.
• 현재 값이 바이토닉 수열을 만족하면 dp = Math.max(dp[i - 1], dp[i]) + 1
• 그런데 올라갔다가 내려오고, 다시 올라가려 하면 0부터 시작해야 하는데.. 이걸 어떻게..

처음 대략 이렇게 코드를 짬

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

문제 정답

• 해결법은 올라갈 때와 내려갈 때를 따로 분리해서 DP 테이블을 만든다.
• 근데 이게 왜 되는건지 몰랐는데, 123421 에서 가장 긴 부분은 1234 = 4이고 감소하는 부분은 421 3 이니까 결과적으로 답은 7 - 1(겹치는 부분인 4를 빼기 위함) = 6이다.

코드

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

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());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] arr = new int[N];
        for (int i = 1; i <= N; i++) {
			arr[i - 1] = Integer.parseInt(st.nextToken());
		}

		int[] inc = new int[N];
		Arrays.fill(inc, 1);

		int[] dec = new int[N];
		Arrays.fill(dec, 1);

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

		for (int i = N - 2; i >= 0; i--) { // 뒤에서 앞으로
			for (int j = N - 1; j > i; j--) {
				if (arr[j] < arr[i]) {
					dec[i] = Math.max(dec[i], dec[j] + 1);
				}
			}
		}
		
		int maxLength = 0;
		for (int i = 0; i < N; i++){
			maxLength = Math.max(maxLength, inc[i] + dec[i] - 1);
		}

		System.out.println(maxLength);

	}

}