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

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

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

 

1. 문제

 

수열 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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

---

2. 입력

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

10
1 5 2 1 4 3 4 5 2 1

---

3. 출력

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

7

---

4. 풀이

이 문제는 앞서 푼 가장 긴 증가하는 수열 문제를 데칼코마니해서 각 인덱스를 기준으로 왼쪽으로는 증가수열, 오른쪽으로 감소 수열인 길이들을 구해 더한 후 -1해주면(-1을 해주는건 기준점은 중복으로 세어지기 때문이다.) 그 길이들에 대한 DP값들을 구할 수 있다.

 

---

5. 소스코드

<Top-Down 방식>

 

import java.io.*;
import java.util.*;
 
public class Main {
	static Integer [][] dp;
    static int [] arr;
	static int N;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
        arr = new int [N];
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<N; i++) arr[i] = Integer.parseInt(st.nextToken());

        dp = new Integer [N][2];

        int result = Integer.MIN_VALUE;
        
        for(int i=0; i<N; i++){
            Lis(i);
            Lds(N-1-i);
        }

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

    public static int Lis(int v){
        if(dp[v][0] == null){
            dp[v][0] = 1;
            for(int i=v; i>=0; i--){
                if(arr[i] < arr[v]) dp[v][0] = (int)Math.max(dp[v][0], Lis(i)+1);
            }
        }
        return dp[v][0];
    }

    public static int Lds(int v){
        if(dp[v][1] == null){
            dp[v][1] = 1;
            for(int i=N-1; i>=v; i--){
                if(arr[v] > arr[i]) dp[v][1] = (int)Math.max(dp[v][1], Lds(i)+1);
            }
        }
        return dp[v][1];
    }
}

ㄴ이때 Lis와 Lds의 for문 범위 설정 시 증감이 딱히 중요치않다는 걸 느꼈다. 어차피 다 돌아가서 적절한 값들을 dp에 할당해주게 될 것이기 때문이다.

 

<Bottom-Up 방식>

import java.io.*;
import java.util.*;
 
public class Main {
	static Integer [][] dp;
    static int [] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
        arr = new int [N];
        
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<N; i++) arr[i] = Integer.parseInt(st.nextToken());

        dp = new Integer [N][2];

        int result = Integer.MIN_VALUE;
        

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

---

6. 배운 것

이전 문제의 단순한 추가 변형문제였기에 크게 배운 것은 없으나 쌍방향에 대한 문제를 풀어야 할 땐 기준점을 두고 반반씩 양쪽으로 계산한 후 합쳐서 그 크기를 비교하면 된다는 것을 알고 가는 기회가 되었다. 또한 중복점이 존재하는지 여부를 확인해볼 필요성도 느꼈다.