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

문제

BOJ 11503. 가장 긴 증가하는 부분 수열

풀이

DP O(n^2)
이분탐색 O(nlogn)

JAVA코드

(1) DP

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

public class 백준11503_가장긴증가하는부분수열 {

	static int N;
	static int[] arr;
	static int[] length;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		length = new int[N];
		int max = Integer.MIN_VALUE;
		
		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++) {
			length[i]=1; // 길이 초기화
			for(int j=0;j<i;j++) {
				if(arr[i]>arr[j]) {
					length[i] = Math.max(length[j]+1, length[i]);
				}
			}
			max = Math.max(max, length[i]);
		}

		
		System.out.println(max);
	}

}

(2) 이분탐색

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

public class 백준11503_가장긴증가하는부분수열_이분탐색 {
	static int N,max;
	static int[] arr;
	static int[] result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		result = new int[N];
		max = Integer.MIN_VALUE;
		
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		
		max = LIS()+1;
		System.out.println(max);
	}
	
	public static int binarySearch(int left,int right,int target) {
		
		int mid=-1;
		
		while(left<right) {
			mid = (left+right)/2;
			if(result[mid]<target) {
				left = mid+1;
			}else {
				right = mid;
			}
		}
		
		return right;
	}
	public static int LIS() {
		int j=0;
		result[0] = arr[0];
		int i=1;
		while(i<N) {
			if(result[j]<arr[i]) {
				result[j+1] = arr[i];
				j+=1;
			}else {
				int idx =  binarySearch(0,j,arr[i]);
				result[idx] = arr[i];
			}
			i+=1;
		}
		
		return j;
	}
}