[백준] 11053 : 가장 긴 증가하는 부분 수열

문제 출처: https://www.acmicpc.net/problem/11053

---

문제

---

시도

 

배열의 첫 번째 요소부터 마지막 요소까지 각각 자기 위치에서 마지막까지 찾아가는 방법을 생각했으나 일단 이중 반복문으로 시간 복잡도가 O(n^2)여서 절대 좋은 결과는 안 나올거라고 생각해 동적 계획법에 관한 블로그부터 다시 찾아봤다.

---

풀이

 

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

public class Main {
    private static int[] arr; // 원 배열
    private static int[] lis; // LIS 길이 저장
    private static int[] V;    // 이전 인덱스 저장

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];
        lis = new int[n];
        V = new int[n];

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

        int result = dp();
        System.out.print(lis[result]);
    }

    public static int dp() {
        // 최대 lis 길이 값
        int max_lis = 0;

        // 최대 길이를 만족시키는 부분 수열의 마지막 인덱스, 초기는 0
        int last = 0;

        // lis[0]은 정했으니 그 이후부터 채우기
        for(int i = 0; i < arr.length; i++) {
            lis[i] = 1;    // 기본 1로 초기화
            V[i] = -1;    // 기본 -1로 초기화

            for(int j = i-1; j >= 0; j--) {
                if(arr[j] < arr[i] && lis[j] >= lis[i]) {
                    lis[i] = lis[j] + 1;
                    V[i] = j; // 이전 인덱스 저장
                }
                if(max_lis < lis[i]) {
                    max_lis = lis[i];
                    last = i;
                }
            }
        }
        return last;
    }
}

 

기존 배열 arr와 각 위치에서 가장 긴 수열에 대한 정보를 담고 있는 lis, 그리고 자신의 바로 전에 해당하는 수열 값의 위치를 담고 있는 배열인 V로 나뉘었다.

 

 

참고 출처: https://hongjw1938.tistory.com/58

---

알게 된 점

 - 점화식과 메모이제이션에 항상 신경써야 하는 문제였다.