[백준] DP - 11054번, 가장 긴 바이토닉 부분 수열 (다른 풀이 봄)

* 공부 목표

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

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

---

풀이

1. 처음 생각해서 망한 풀이

• k = Max 값 || SecondMax값
• k값 이전까지는 증가 부분 수열, k값 이후에는 감소 부분 수열
• k가 Max일 때와 SecondMax일 때 중 더 긴 쪽이 정답

예제에 나온 답 제외하고 다른 반례는 맞게 출력됐다.

 

어떤 부분이 문제였나?

수열 내 Max값이 2개 이상 있을 때 기준이 되는 k가 먼저 나온 값이 됨.

따라서 바이토닉 수열은 맞지만 <가장 긴 수열>은 아니므로 정답이 아니게 됨.

(사실 이게 아니더라도 너무 길고 재사용성 낮은 코드라 런타임 에러 떴을 확률이 높았음.)

 

 

2. 다른 풀이의 아이디어

• 오름차순 부분 수열, 내림차순 부분 수열을 각각 구한다.
• 두 개의 부분 수열을 합한다.
• 누적된 값(dp[i]) 중 최댓값을 구한다. ➡️ 결과
• 원소가 1개씩 중복되어 있으므로 결과에서 -1을 해줘야 정답

 

코드

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

public class Main {
    static int n;
    static int[] arr;
    static int[] first;
    static int[] after;

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

        first();
        after();

        //max 값 찾기
        int max = 0;
        for(int i=0; i<n; i++) {
            max = (max < first[i] + after[i]) ? first[i] + after[i] : max;
        } System.out.println(max - 1);
        br.close();
    }
    public static void first() {
        for(int i=0; i<n; i++) {
            first[i] = 1;
            for(int j=0; j<i; j++) {
                if(arr[j] < arr[i] && first[i] < first[j] +1) first[i] = first[j] + 1;
            }
        }
    }
    public static void after() {
        //시작이 뒤
        for(int i=n-1; i >= 0; i--) {
            after[i] = 1;
            for(int j=n-1; j>=0; j--) {
                if(arr[j] < arr[i] && after[i] < after[j] +1) after[i] = after[j] + 1;
            }
        }
    }
}

 

---

 

각 수열을 따로 구해 더한다는 개념은 생각하지 못해서 충격이었다.🥹

머리 쥐어 싸매며 고민해도, 구상이 잘못되면 처음부터 새로 해야한다.

 

열심히... 더 많이...  배워야겠다.

 

[참고] https://st-lab.tistory.com/136