가장 긴 증가하는 수열 ( 백준 11053 )

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

 

* 시리즈 1, 2가 존재하는데 1은 입력값이 크지않고 2는 입력값이 크다

* 따라서 1은 이중 반복문을 사용하는 dp를 사용해도 해결된다

* 2는 입력값이 크기 때문에 binarySearch를 이용한 lowerBownd 탐색으로 해결 해야한다

 

* 기본적으로 브루트포스를 진행하면서 큰값이 나오면 dp 배열에 저장하는 것

* 시간 복잡도는 O(N^2)

 

 

* i를 중심으로 j는 i보다 작은값만 탐색한다

* 그 중에 증가하는 경향 즉 arr[i] > arr[j] 조건이 성립되면 dp[i]에 +1 할당한다.

* 아이디어는 좋지만 이중 for() 이기 때문에 입력값이 크게 되면 LIS2를 사용해야함.

 

* 코드

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

class BOJ12015 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        int[] arr = new int[size], dp = new int[size];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.fill(dp, 1);
        for(int i = 1; i < size; i++) {
            for(int j = 0; j < i; j++) {
                if(arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        int res = Integer.MIN_VALUE;
        for(int i = 0 ; i < size; i++) {
            res = Math.max(res, dp[i]);
        }
        System.out.println(res);
    }
}