[BaekJoon] 11054번 가장 긴 바이토닉 부분 수열 (Java) 문제 풀이 [Gold 4]

문제

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

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

 

어떻게 풀 것인가?

LIS와 LDS의 혼합 문제였다.

처음에 LIS를 시행이후에 LDS를 시행하면 문제가 원하는 최장 바이토닉 수열의 길이가 나온다.

간단했다.

아래는 LIS 와 LDS의 정리글이다.

https://superohinsung.tistory.com/199

[Algorithm] LIS, LDS (최장 증가 부분 수열, 최장 감소 부분 수열)

풀면서 놓쳤던점

LIS와 LDS에 대한 개념 접근을 처음에는 까먹고 있어서 조금 헤맸다.

시간이 된다면 블로그에 정리했던 알고리즘들을 다시 공부해야할 것 같다.

 

이 문제를 통해 얻어갈 것

LIS, LDS에 대한 개념

 

내 코드 

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

// 백준알고리즘 11054번 가장 긴 바이토닉 부분 수열
public class Main {
    static int N;
    static int[] arr;
    static int[] Rdp;
    static int[] Ldp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[N];
        Rdp = new int[N];
        Ldp = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        LIS();
        LDS();

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

    static void LIS() {

        for (int i = 0; i < N; i++) {
            Rdp[i] = 1;

            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && Rdp[i] < Rdp[j] + 1) {
                    Rdp[i] = Rdp[j] + 1;
                }
            }
        }
    }

    static void LDS() {

        for (int i = N - 1; i >= 0; i--) {
            Ldp[i] = 1;

            for (int j = N - 1; j > i; j--) {
                if (arr[j] < arr[i] && Ldp[i] < Ldp[j] + 1) {
                    Ldp[i] = Ldp[j] + 1;
                }
            }
        }

    }
}

 

참고

https://velog.io/@49crehbgr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-LIS-LDS

[알고리즘/Algorithm] LIS, LDS