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

백준 바로가기

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

DP 알고리즘 내 LIS(Longest Increasing Subsequence) 최장 증가 수열 문제입니다. 이해하는데 하루 꼬박걸렸으며 이해까지 도달하는데 효과적인 매체는 아래 유튜브 강의였습니다. 설명이 영어라도 그림만 봐도 이해되는 강의라 보심을 추천드립니다. 링크

출처: https://www.youtube.com/watch?v=CE2b_-XfVDk&list=LL&index=8&t=311s

 

풀이의 골자는 주어진 수열을 중첩 반복문으로 돌면서 각 index 값을 이전 값들과 대소 비교하여 LIS 값을 dp 배열에 저장해주는 것입니다. 헌데 대소 비교에서 나아가 수열이 '증가' 해야만 되는 특징이 있기 때문에 조건이 하나 더 추가됩니다. 아래 2) 문제 해결 로직에서 설명하겠습니다. 

1) 데이터 '틀'

LIS 수열은 총 3개 배열로 나누어 선언해주었습니다. 본 문제는 기본 최장 수열 + 거꾸로 최장 수열 유형이기 때문인데요. 무슨 말이냐면 바이토닉 부분 수열은 증가하다가 감소할 경우에도 길이에 포함되기 때문입니다. 글보다 그림이 나아 백준 힌트화면을 공유해드릴게요. 

내가 설정한 데이터 변수들

 

바이토닉 부분 수열 = 기본 최장 수열 + 거꾸로 최장 수열

거꾸로 최장 수열의 의미는 왼쪽 -> 오른쪽 순서로 증가 수열을 반대로 오른쪽 -> 왼쪽 증가 수열로 시작과 끝을 반대로 해서 구해준다는 뜻입니다. 쉽게 생각하면 내리막길은 반대편에서 시작했을 때 오르막길이 되는 것과 같은 원리를 사용하는 것이죠.

따라서 최종 통합 LIS 수열은 2가지 수열의 LIS 값을 더한 값이 되는 것입니다! 

2) 문제 해결 로직

LIS 원리가 이해되셨다면 DP 알고리즘에 적용할 차례입니다. 17행의 왼 -> 오 순서로 증가하는 최장 수열을 구하는 중첩 반복문 입니다. 최소 LIS는 자기 자신이 될 수 있기 때문에 dpIn[i] 배열 값은 1로 초기화 해줍니다. i번째 수열 값과 0~i번째까지 수열을 대소 비교해 그보다 작은 값이 있다면 점화식을 실행합니다. 21행의 점화식은 위 유튜브 영상을 보시면 알 수 있습니다. 증가식의 특성이 그 이유인데요 자세한 글로 설명해볼게요. 모르시겠으면 영상을 바로 보시는 것을 강려크하게 추천드립니다.

여기서 대소 비교할 때 값만 크면 무조건 LIS 값이 + 1 되는 것이 아니라 이미 반복문으로 비교한 j 값보다 더 큰 값이어야만 LIS가 + 1 되어야 합니다. 예를 들어 주어진 수열이 1 2 3 2 4 일 때, 현재 i 가 4라고 정하죠. 반복문은 1 2 3 2 4를 차례로 j 값에 넣어 i번째 값 4와 대소 비교하게 됩니다. 이 때 3번째 index 2와(index는 0번째부터 시작) 비교하게 되었을 때 dpIn[3]은 LIS가 2이며, 현재 i번째 dpIn[4] LIS는 1 2 3 2 4 과 비교를 마친 상태여서 LIS 값이 3 입니다. 따라서 Math API max 메서드를 사용해 자신보다 작은 값을 때, 자신의 LIS보다 클 때만 LIS + 1을 반복해나가는 것입니다!

26행은 오 -> 왼 순서대로 최장 수열을 얻는 중첩 반복문이구요, 17행 반복문과 완전히 동일하며 시작과 끝이 다를 뿐입니다. 36행부터 38행까지는 두 최장 수열 값을 더해 최종 통합 LIS 수열을 만들어 주는 반복문입니다. 

마지막으로 40행은 최종 LIS 수열 deSum[] 배열에서 가장 큰 값을 찾아 max 변수에 담는 과정이며, 두 최장 수열 값을 구할 때 정점이 되는 수가 두 번 더해지기 때문에 답안 출력 할 땐 max - 1을 sysout 해주었습니다. 감사합니다 :) 

3) 정답 코드

public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr1 = new int[n];
        dpIn = new int[n];
        dpDe = new int[n];
        dpSum = new int[n];
 
        for (int i = 0; i < n; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 0; i < n; i++) {
            dpIn[i] = 1;
            for (int j = 0; j <= i; j++) {
                if (arr1[i] > arr1[j]) {
                    dpIn[i] = Math.max(dpIn[i], dpIn[j] + 1);
                }
            }
        }
 
        for (int i = n - 1; i >= 0; i--) {
            dpDe[i] = 1;
            for (int j = n - 1; j >= i; j--) {
                if (arr1[i] > arr1[j]) {
                    dpDe[i] = Math.max(dpDe[i], dpDe[j] + 1);
                }
            }
        }
 
 
        for (int i = 0; i < n; i++) {
            dpSum[i] = dpIn[i] + dpDe[i];
        }
 
        for (int ele :
                dpSum) {
            if (ele >= max) {
                max = ele;
            }
        }
 
        System.out.println(max - 1);
 
    }