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

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

---

내가 푼 방법

가장 긴 증가하는 부분수열과 감소하는 부분수열을 합친 문제이다.

나는 기준점 (idx) 을 잡아 그 기준점보다 낮은 인덱스는 LIS 알고리즘을

그리고 높은 인덱스는 LIS를 뒤집어 사용하여 감소하는 부분 수열을 구현하였다.

 

10
1 5 2 1 4 3 4 5 2 1

만약 위 예제에서 idx = 3을 조사한다 하면 arr[3]을 기준으로

{ 1, 5, 2 } 를 오름차순 긴 부분수열을 구하고,  { 2, 1, 4, 3, 5, 2, 1 } 을 내림차순 긴 부분수열을 구한다

이렇게 구한 오름차순과 내림차순 수열길이를 합한 값에 -1을 하면 바이토닉 수열이 나온다.

( 자신값을 두번 계산했기 때문에 1을 빼줘야한다. )  

 

이렇게 기준점 idx를 잡고 while문에 LIS알고리즘( O(N^2) )을 계산했더니

역시 1000번 입력이라도 속도가 엄청 느려졌다. 

지금 다시보니 통과한게 신기할 정도

 

 

새로운 방법

올라갔다가 내려가는 수열을 구하려면

우선 오름차순 부분 수열과(LIS) 내림차순 부분수열 (LDS)을 구해야한다

10
1 5 2 1 4 3 4 5 2 1

위와 같은 예제를 다시 풀어보면

오름차순으로 구할 시 

ascDP = { 1, 2, 2, 1, 3, 3, 4, 5, 2, 1 } 을 가진다.

즉 ascDP[ 7 ] 일때 { 1, 2, 3, 4, 5 } 5의 길이를 가진 가장 긴 수열이 나온다

 

이번엔 내림차순으로 구하면

descDP = { 1, 5, 2, 1, 4, 3, 3, 3, 2, 1 } 을 가진다

 

여기서 오름차순 수열과 내림차순 수열을 더하면 오름차순과 내림차순이 합쳐진 수열이 나온다.

주의해야 할 점은 위와 같이 하나의 원소가 중복되어 결과가 나온다. 

( dp[2]를 구하면 두번째 원소가 중복된다 )

result = { 1, 6, 3, 1, 6, 5, 6, 7, 3, 1 }

 

이 방법으로 풀면 O(N^2) 의 시간복잡도를 가져 시간이 훨씬 단축된다

---

이전 풀이

기준점으로 나눈 후 내림차순 오름차순 구한 코드

// https://www.acmicpc.net/problem/11054
// 가장 긴 바이토닉 부분 수열

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

public class B11054_slow {
    static int N;
    static int[] res;
    static int[] dp;
    static int[] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        board  = new int[N+1];
        dp = new int[N+1];

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

        int idx = 1;
        res = new int[N+1];
        int result = 1;
        while(idx<=N) {
            // 기준점을 오름차순과 내림차순에 넣거 값 구하기
            res[idx] = asc(idx) + desc(idx) -1;
            // 결과 저장
            if(result<res[idx]) result = res[idx];
            // idx 값 증가시키기
            idx++;
        }
        System.out.println(result);
        br.close();
    }

    // LIS
    private static int asc(int idx){
        dp = new int[N+1];
        dp[1] = 1;
        int res = 1;

        for (int i = 2; i <= idx; i++) {
            dp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (board[i] > board[j] && dp[i] <= dp[j]) {
                    dp[i] +=1;
                }
            }
            res = Math.max(res , dp[idx]);
        }
        return res;
    }
    
    private static int desc(int idx){
        dp = new int[N+1];
        dp[N] = 1;
        for (int i = N-1; i >= idx; --i) {
            dp[i] = 1;
            for (int j = N; j > idx; --j) {
                if (board[i] > board[j] && dp[i] <= dp[j]) {
                    dp[i] += 1;
                }
            }
        }
        return dp[idx];
    }
}

 

새로운 풀이

바이토닉 부분수열 구하기

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

public class B11054 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] board  = new int[N+1];
        int[] ascDp = new int[N+1];
        int[] descDp = new int[N+1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            board[i] = Integer.parseInt(st.nextToken());
        }
        // 오름차순 결과 구하기
        ascDp[1] = 1;
        for (int i = 2; i <= N; i++) {
            ascDp[i] = 1;
            for (int j = 1; j < i; j++) {
                if (board[i] > board[j] && ascDp[i] <= ascDp[j]) {
                    ascDp[i] +=1;
                }
            }
        }
        // 내림차순 결과 구하기
        descDp[N] = 1;
        for (int i = N-1; i >= 1; --i) {
            descDp[i] = 1;
            for (int j = N; j > i; --j) {
                if (board[i] > board[j] && descDp[i] <= descDp[j]) {
                    descDp[i] += 1;
                }
            }
        }
        // 오름차순 + 내림차순 중 가장 큰값 구하기
        // 결과에 -1
        int res = 1;
        for (int i = 0; i <= N; i++) {
            res = Math.max(res, (ascDp[i]+descDp[i]) );
        }
        System.out.println(res-1);
    }
}