[BOJ] 11053. 가장 긴 증가하는 부분 수열

LIS의 대표적인 예제 문제이다.

LIS를 구현함에 있어 크게 n^2의 시간복잡도를 가지는 dp, nlogn의 시간복잡도를 가지는 lower_bound가 있다. 이 문제 같은 경우는 n의 최대 크기가 1000이기에 dp를 이용하여 풀어보았다.

dp를 이용하여 푸는 경우 LIS배열을 하나 생성한다. 이 LIS 배열의 경우 LIS[i]가 나타내는 것은 arr[i]를 마지막으로 가지는 가장 긴 수열의 길이를 의미하게 된다. 즉, 위의 예제입력을 예로 들면 LIS[5]의 경우 arr[5]의 값 즉 50을 가장 마지막으로 가지는 최장 증가 수열의 길이를 의미하게 된다. 이것을 확인하는 원리는 기준의 되는 인덱스 i에 대해 비교 인덱스 j를 두고 1. j<i  2. arr[j]<arr[i] 이 두가지 조건을 모두 만족하게 되는 경우 LIS[i] 값을 갱신해주는 방법을 사용하게 된다. 코드는 다음과 같다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_11053_가장긴증가하는부분수열 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        int N = Integer.parseInt(br.readLine());
 
        int[] arr = new int[N];
        int[] LIS = new int[N];        //LIS[i]는 arr[i]를 마지막으로 가지는 가장 긴 수열의 길이
 
        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] = 1;
 
            //arr[i]를 마지막으로 가진다라는 조건을 만족할려면 j<i 이고, arr[j]<arr[i]이여야 한다
            //따라서 LIS[i]를 갱신하기 위해 위의 두 조건을 확인한다
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    LIS[i] = Math.max(LIS[i], LIS[j] + 1);
                }
            }
        }
 
        int answer = 0;
        for (int i = 0; i < N; i++) {
            answer = Math.max(answer, LIS[i]);
        }
 
        System.out.println(answer);
    }
}
 

 

위의 LIS 코드에 추적을 더한 코드는 다음과 같다.

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Deque;
import java.util.LinkedList;
import java.util.StringTokenizer;
 
public class Main_bj_14002_가장긴증가하는부분수열4 {
    static class Node {
        int value;
        int prevIndex;
 
        public Node(int value, int prevIndex) {
            this.value = value;
            this.prevIndex = prevIndex;
        }
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        int N = Integer.parseInt(br.readLine());
 
        int[] arr = new int[N];
        int[] LIS = new int[N];        //LIS[i]는 arr[i]를 마지막으로 가지는 가장 긴 수열의 길이
        Node[] nodes = new Node[N];
 
        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] = 1;
            nodes[i] = new Node(arr[i], -1);
            //arr[i]를 마지막으로 가진다라는 조건을 만족할려면 j<i 이고, arr[j]<arr[i]이여야 한다
            //따라서 LIS[i]를 갱신하기 위해 위의 두 조건을 확인한다
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i] && LIS[i] < LIS[j] + 1) {
                    LIS[i] = LIS[j] + 1;
                    nodes[i] = new Node(arr[i], j);
                }
            }
        }
 
        int longestLength = 0;
        int longestLengthIndex = 0;
 
        for (int i = 0; i < N; i++) {
            if (longestLength < LIS[i]) {
                longestLength = LIS[i];
                longestLengthIndex = i;
            }
        }
 
        Deque<Integer> result = new LinkedList<>();
 
        for (int i = 0; i < longestLength; i++) {
            result.addFirst(nodes[longestLengthIndex].value);
            longestLengthIndex = nodes[longestLengthIndex].prevIndex;
        }
 
        System.out.println(longestLength);
        for (int i = 0; i < longestLength; i++) {
            System.out.print(result.removeFirst() + " ");
        }
 
    }
}