[백준] 11504_가장 긴 바이토닉 부분 수열 / 동적계획법, LIS

 

 

Gold

 

 

문제

수열 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의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

 

 

 

---

 

풀이

 

import java.util.*;
import java.io.*;

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

        // dp1[i]: i번째 요소를 끝으로 하는 최장 증가 부분 수열의 길이
        int[] dp1 = new int[N];
        Arrays.fill(dp1, 1);
        for(int j=1; j<N; j++){
            for(int i=0; i<j; i++){
                if(arr[i]<arr[j]){
                    dp1[j] = Math.max(dp1[i]+1, dp1[j]);
                }
            }
        }

        // dp2[i]: i번째 요소를 시작으로 하는 최장 감소 부분 수열의 길이
        int[] dp2 = new int[N];
        Arrays.fill(dp2, 1);
        for(int j=N-2; j>=0; j--){
            for(int i=N-1; i>j; i--){
                if(arr[i]<arr[j]){
                    dp2[j] = Math.max(dp2[i]+1, dp2[j]);
                }
            }
        }

        int max = 0;
        for(int i=0; i<N; i++){
            max = Math.max(dp1[i]+dp2[i]-1, max);
        }
        
        System.out.println(max);
    }
}

 

해결방법

1. dp1에 i번째 요소를 끝으로 하는 최장 증가 부분수열의 길이를 저장한다.
2. dp2에 i번째 요소를 시작으로 하는 바이토닉 최장 감소 부분수열의 길이를 저장한다. 
3. dp1과 dp2를 각각 계산한 후, dp1[i] + dp2[i] - 1의 최댓값을 구해 바이토닉 부분 수열의 최장 길이를 찾는다.

 

 

 

---

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