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

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력 1 복사

10
1 5 2 1 4 3 4 5 2 1

예제 출력 1 복사

7

나의 풀이

이 문제는 앞에서 풀었던 가장 긴 부분수열문제와 비슷하지만 조건이 추가되어서 살짝 다르게 풀어야했다. 우선 다이나믹 프로그래밍 문제로 점화식을 세워야겠다는 생각과 앞에서 구한 최댓값들을 활용하여 최댓값을 계속 구해나간다는 생각부터 시작했다.

위에서의 바이토닉 수열이 되기위해서는 증가하다가는 감소하는 수열로 바뀔 수 있지만 감소를 하다가는 다시 증가를 할 수가 없다는 조건을 찾으니 쉽게 풀 수 있었다. 나는 이 문제를 풀기위해서 dp배열을 n+1 * 2의 형태로 만들어 [0]에는 증가를 할때의 최댓값을 저장하고 [1]에는 감소를 할때의 최댓값을 저장해나갔다. 여기서 키포인트는 앞에서 말한 증가하다가 감소로 바뀔 수 있다는 점이다. 따라서 감소할때의 최댓값을 구할때에는 증가하다가 감소하는 것을 생각해 증가할때의 최댓값과도 비교를 해봐야한다는 점이다. 아래에 점화식을 보면 쉽게 이해가 갈 것이다.

// i번째 수 > j번째 수 (증가를 하는 경우)
dp[i][j] = Math.max(dp[i][0],dp[j][0]+1);

// i번째 수 < j번째 수 (감소를 하는 경우)
dp[i][1] = Math.max(dp[i][1],Math.max(dp[j][1]+1,dp[j][0]+1));

코드

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

/**
 * 11054번 가장 긴 바이토닉 부분 수열
 */
public class Baeckjun11054 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] dp = new int[n+1][2];
        int[] seq = new int[n+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=1; i<=n; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }

        int answer = 1;
        for (int i=1; i<=n; i++) {
            dp[i][0] = dp[i][1] = 1;
            for (int j=1; j<i; j++) {
                if (seq[j] < seq[i]) {
                    dp[i][0] = Math.max(dp[i][0],dp[j][0]+1);
                }
                else if (seq[j] > seq[i]) {
                    dp[i][1] = Math.max(dp[i][1],Math.max(dp[j][1]+1,dp[j][0]+1));
                }
            }
            answer = Math.max(answer,Math.max(dp[i][0],dp[i][1]));
        }

        System.out.println(answer);
    }
}