[백준] 11054 - 가장 긴 바이토닉 부분 수열(Java)

문제 파악

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

풀이

DP문제이며 푸는데 오래 걸리지는 않았으나,
문제에서 놓친 부분이 있어 마지막에 정답을 계산하는 과정에서 조금 헤맸다. 문제를 잘 읽도록 하자 ^_^

가장 먼저 오름차순, 내림차순의 길이를 저장하는 DP 배열을 각각 선언해 준다.
DP는 "해당 자리의 숫자를 포함"하여 오름차순, 내림차순을 만족하는 수열의 길이를 저장한다.

증가(혹은 감소) 수열을 만족했을 때 DP값에서 1을 더해 현재 DP에 저장하도록 하자.
오름차순은 인덱스가 증가하는 방향으로, 내림차순은 감소하는 방향으로 순회하도록 했다.

다음 {1,2,2,3,1,4} 수열을 예로 들어 보았다.

마지막으로 정답은 각각의 자리의 오름차순, 내림차순 DP를 더해 준 다음 1을 빼 준 값이 된다.
1을 빼주는 이유는 오름차순 DP, 내림차순 DP 모두 현재 위치의 원소를 포함하기에 중복을 제거해주는 과정이다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());
        int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] ascDP = new int[count];
        int[] descDP = new int[count];
        Arrays.fill(ascDP, 1);
        Arrays.fill(descDP, 1);
        // asc
        for (int i = 0; i < count; i++) {
            for (int j = 0; j < i; j++) {
                if (input[i] > input[j]) {
                    ascDP[i] = Math.max(ascDP[i], ascDP[j] + 1);
                }
            }
        }
        // desc
        for (int i = count - 1; i >= 0; i--) {
            for (int j = i + 1; j < count; j++) {
                if (input[i] > input[j]) {
                    descDP[i] = Math.max(descDP[i], descDP[j] + 1);
                }
            }
        }
        System.out.println(IntStream.range(0, count)
                .map(i -> descDP[i] + ascDP[i] - 1).max().orElse(1));
    }
}