[백준] 상자넣기 1965 - JAVA

문제

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

1965번: 상자넣기

 

풀이

이 문제는 최장 증가 부분 수열(LIS)를 구하는 문제다.

최장 증가 부분 수열은 dp를 이용하여 풀면 O(N^2)의 시간 복잡도가 나온다.(이분탐색을 이용하면 O(nlogn))

 

코드

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

public class Main {
	
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

       	int n = Integer.parseInt(br.readLine());
       	
       	int arr[] = new int[n+1];
       	int dp [] = new int[n+1];
       	
       	st = new StringTokenizer(br.readLine());
       	
       	for(int i=1;i<=n;i++) {
       		arr[i] = Integer.parseInt(st.nextToken());
       	}
       	
       	for(int i=1;i<=n;i++) {
       		dp[i] = 1;
       		for(int j=1;j<i;j++) {
       			if(arr[j] < arr[i]) {
       				dp[i] = Math.max(dp[i], dp[j]+1);
       			}
       		}
       	}

       	Arrays.sort(dp);
       	
       	System.out.println(dp[n]);
       	
   }
   
   
}