[백준] no11504:바이토닉 수열 - 바이토닉 정렬(Bitonic)

문제

주어진 수열에서 구할 수 있는 바이토닉 수열의 최대길이를 구하기

 

바이토닉 수열 : 수열 내 요소가 순차적으로 증가하다가 감소하는 수열

즉, {0,1,2,3,4,3,2,1}, {0,1,2,3}, {4,3,2,1}은 바이토닉 수열 O

단, {0,1,3,2,4,3,2,1}, {0,1,2,3,2,4,0}은 바이토닉 수열 X 

---

원리

         * 1. arr에 대해, 0번 인덱스~N-1번 인덱스까지 도달하면서 오름차순으로 가장 길게 얻을 수 있는 길이를 기록하는 DP를 실행
         * 2. 반대 방향으로 DP실행
         * 3. 두 수열의 값을 합치면 바이토닉 수열의 최대값들이 기록된 DP 배열이 됨.
         * 4. 단, 각 위치별 중복값을 포함하게 되므로, 각 위치 최대값에 대해 -1을 해줘야 함

 

---

나의 코드

[실패] 1차시도 : DFS를 이용한 조건문 하드코딩

실패원인 : 인덱스 설정 오류, 코드 실행에 따른 메모리 소모 심함(브루트 포스이기 때문)

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * 각 숫자에 대해 DFS 실행
 *
 * DFS 조건
 * 1. 현재 list의 마지막 값보다 다음 값이 더 크다면 증가 유지
 * 2. 현재 list의 마지막 값보다 다음 값이 더 작다면 감소 시작
 * 3. 감소 중 다음 값이 현재 list의 마지막 값보다 더 큰 값이라면, 탐색 종료 후 list의 사이즈를 max값과 비교해서 업데이트
 *
 */
public class no11054 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N;
    private static int[] arr;
    private static StringTokenizer st;
    private static int max_val;

    public static void main(String[] args) throws IOException {

        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        max_val = Integer.MIN_VALUE;

        for(int i=0; i<N ; i++) arr[i] = Integer.parseInt(st.nextToken());

        for(int i=0; i<N ; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(arr[i]);
            DFS(i, list);
        }

        System.out.println(max_val);
        bw.close();
    }

    private static void DFS (int start, List<Integer> list) {

        if(list.size()<=1) {
            List<Integer> temp_list = new ArrayList<>(List.copyOf(list));
            temp_list.add(arr[start+1]);
            DFS(start+1, temp_list);
        }

        for(int i=start+1 ; i<N ; i++) {
            if(list.get(list.size()-1)<arr[i]) {
                if(list.get(list.size()-1)<list.get(list.size()-2)) {
                    max_val = Math.max(max_val, list.size());
                    continue;
                }
                List<Integer> temp_list = new ArrayList<>(List.copyOf(list));
                temp_list.add(arr[i]);
                DFS(i, temp_list);
            }
            else if(list.get(list.size()-1)>arr[i]) {
                List<Integer> temp_list = new ArrayList<>(List.copyOf(list));
                temp_list.add(arr[i]);
                DFS(i, temp_list);
            }
        }
    }
}

 

[성공] 레퍼런스를 참고한 LIS + LDS를 이용한 바이토닉 공식

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

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int[] arr;
    private static Integer[] Rt_DP, Lt_DP;

    public static void main(String[] args) throws IOException {

        int N = Integer.parseInt(br.readLine());
        arr = new int[N];
        Rt_DP = new Integer[N];
        Lt_DP = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

        for(int i=0 ; i<N ; i++) {
            LIS(i);
            LDS(i);
        }

        int max = -1;
        for(int i = 0; i <N ; i++) max =Math.max(Rt_DP[i]+ Lt_DP[i], max);

        System.out.println(max - 1); // 결국 모든 값은 다 -1 해줘야 하므로
    }

    // 순방향 오름차순 부분 수열 구하기
    private static int LIS(int N) {

        // 탐색하지 않았던 곳이면 1로 초기화
        if (Rt_DP[N] == null) {
            Rt_DP[N] = 1;

            // 이전 노드 탐색
            for (int i=N-1; i>=0; i--) {
                //이전 노드 중 작은 값을 발견한 경우
                if(arr[i] < arr[N]) Rt_DP[N] = Math.max(Rt_DP[N], LIS(i)+1);
            }
        }    
        return Rt_DP[N];
    }

    // 역방향 오름차순 부분 수열 구하기
    private static int LDS(int N) {

        // 탐색하지 않았던 곳이면 1로 초기화
        if (Lt_DP[N] == null) {
            Lt_DP[N] = 1;

            // N 이후 노드 탐색
            for (int i=N+1; i<Lt_DP.length; i++) {
                //이후 노드 중 작은 값을 발견한 경우
                if(arr[i] < arr[N]) Lt_DP[N] = Math.max(Lt_DP[N], LDS(i) +1);
            }
        }
        return Lt_DP[N];
    }
}

 

---

레퍼런스

참고링크 1 : LIS 및 LDS를 이용한  풀이 방법 https://st-lab.tistory.com/136