백준 11053번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	256MB	실버 2

사진을 클릭하면 문제로 이동합니다.

---

풀이

 밀린 문제 정리하기. 이번엔 LIS 알고리즘이다. 뭐 사실 dp의 특수형태라고도 할 수 있는데, LIS는 Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열의 약자이다. 말 그대로 전체 수열 S가 주어졌을 때, 이중에서 원소가 증가하는 순서대로 부분 수열들을 구했을 때, 이중에서 가장 긴 부분 수열을 구하는 문제이다.

 

 LIS알고리즘도 언젠간 정리할 예정이다. 말만 하고 안하고 있는 이유는 알고리즘 정리는 내가 그 알고리즘들에 대해 이해도가 높아졌다고 생각이 들 때 정리할 예정이다. 지금의 나는 여러 알고리즘을 사용할줄은 알지만, 제대로된 이해가 없이 그냥 가져다 쓰는 느낌이 많이 들어서 응용문제에선 항상 깨지기만 한다. 이러한 애로사항이 해결되고, 이해도가 올라 응용도 무리없이 가능하다고 생각이 들 때, 알고리즘을 정리할 예정이다. 내실이 다져지면, 나도 다른 고수분들처럼 알고리즘 글을 정리하고 싶다. 그러니 지금은 내실을 다지는 기간이라고 생각하자. 얼마나 걸릴지 모르겠지만 반드시 해낼 수 있을 것이라 생각한다.

 

간단히 설명하자면 dp로 생각했을 때 S의 0번째 원소부터 i번째 원소까지 살펴봤을 때의 lis를 계속해서 찾아보는 것이다. 물론 i를 증가시킴에 따라 0 ~ i-1번째 원소를 살펴보는 것은 O(N^2)의 시간복잡도가 걸릴테고, 나중에 응용하는 문제가 나오면 반드시 터질 것이다. 그러니 우리는 더 빠르게 개선해야한다. 물론 이 문제에서는 N이 1000밖에 안되기 때문에 상관은 없지만, 나중을 위해 개선된 방식을 공부하자. lis라는 배열을 하나 만든 후, 해당 배열에 lis를 계속해서 저장한다. 정확히는 lis가 아닌 lis가 될 수 있는 후보들을 저장하는 배열이다. 해당 배열에 오름차순으로 후보들을 저장하고, 이분탐색을 통해 계속해서 갱신한다. 이렇게만 말하니 이해가 잘 안 될 것이다. 그러니 내가 알고리즘을 정리하기전까진, 다른 분들 설명 같이 보는게 좋을 것 같다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

int n;
vector<int> arr;

void input() {
	cin >> n;
	arr.resize(n);
	for(int& x : arr) cin >> x;
}

void sol() {
	vector<int> lis{0}, dp(n, 0);

	for(int i = 0; i < n; i++) {
		if(lis[lis.size() - 1] < arr[i]) {
			lis.push_back(arr[i]);
			dp[i] = lis.size() - 1;
		}
		else {
			int idx = lower_bound(ALL(lis), arr[i]) - lis.begin();
			lis[idx] = arr[i];
			dp[i] = idx;
		}
	}
	cout << lis.size() - 1;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}