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

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

11053번: 가장 긴 증가하는 부분 수열

 

 

0. 알고리즘 분류

 다이나믹 프로그래밍

 

 

1. 문제

 

 

2. 풀이

 제목에서 보이다시피, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence) 문제이다. 개념을 몰라서 구글링으로 배웠다. 하나의 배열을 만들고, 여기에 입력값을 증가하는 순으로 쌓는다. 만약 작은 값이 들어오면 이분탐색으로 들어갈 수 있는 위치를 찾고, 그 위치에 값을 넣는다. 이를 반복해서 가장 긴 증가하는 부분 수열의 길이를 알 수 있다.

 

 

3. 코드

#include <iostream>

using namespace std;

int length[1001];

int binarySearch(int left, int right, int target) {
	int mid;
	
	while (left < right) {
		mid = (left + right) / 2;
		
		if (target > length[mid]) {
			left = mid+1;
		}
		else {
			right = mid;
		}
	}
	
	return right;
}

int main(void) {
	int n;
	cin >> n;
	
	int arr[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	
	int ix = 0;
	length[ix] = arr[0];
	
	for (int i = 1; i < n; i++) {
		if (length[ix] < arr[i]) {
			length[++ix] = arr[i];
		}
		else {
			int temp = binarySearch(0, ix, arr[i]);
			length[temp] = arr[i];
		}
	}
	
	cout << ix+1;
	
	return 0;
}