[백준] 12738번: 가장 긴 증가하는 부분 수열 3 (c++)

 

문제

---

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

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

 

문제조건

---

• N (1 ≤ N ≤ 1,000,000)
• -1,000,000,000 ≤ Ai ≤ 1,000,000,000

 

풀이

---

N이 1000000이기 때문에 이중 for문(O(\(n^2\)) 시간복잡도)으로는 풀리지 않는다. 시간복잡도가 O(\(logN\))인 이분 탐색을 통해 LIS(Longest Increasing Subsequence)를 찾아야 한다. c++에는 이분탐색 lower_bound가 구현되어 있어 쉽게 사용할 수 있다.

💡 lower_bound: 말 그대로 하한선. 찾으려는 key 값보다 같거나 큰 숫자가 배열에서 언제 처음 등장하는지 찾는 것(index). 단, 탐색을 진행할 배열 혹은 벡터는 오름차순 정렬되어 있어야 한다.

 

문제에서 주어진 예시보다 조금 더 복잡한 예를 통해 LIS를 구하는 과정을 살펴보자. 수열 A = { 10, 50, 60, 20, 30, 40}이라고 하자. 구하고자 하는 증가하는 배열을 V라고 하자.

10

우선 가장 첫번째 값인 10을 배열V에 넣는다.

10

50

다음 값인 50은 배열V의 마지막 값인 10보다 크기 때문에 값을 넣을 수 있다.

10

50

60

다음 값인 60은 배열V의 마지막 값인 50보다 크기 때문에 값을 넣을 수 있다.

10

20

60

여기서부터가 포인트다. 값 20은 배열V의 마지막 값인 60보다 작다. 이때 lower_bound를 사용해서 20이 들어갈 수 있는 위치를 찾아준다. 배열 V는 항상 증가만 하도록 값을 넣어주고 있기때문에 오름차순으로 정렬되어 있어 lower_bound를 사용할 수 있다. 20은 10과 50 사이의 수라서 lower_bound는 인덱스 1을 리턴한다. 이 위치에 숫자 20을 넣어주자.

10

20

30

값 30은 배열V의 마지막 값인 60보다 작다. 30은 20보다 크고 60보다 작기 때문에 lower_bound는 인덱스 2을 리턴한다. 이 위치에 숫자 30을 넣어주자.

10

20

30

40

다음 값인 40은 배열V의 마지막 값인 30보다 크기 때문에 값을 넣을 수 있다.

이진탐색을 사용하기때문에 보다 빠르게 정답을 찾을 수 있다. 길이를 구하는 문제이기 때문에 위와 같은 풀이는 12738번 문제의 정답이다. 하지만 이렇게 구한 값은 정확하게 LIS는 아니다. 다른 예시인 A = { 10, 40, 50, 30 }에 대한 증가하는 배열 V를 구해보면 [10] -> [10, 40] -> [10, 40, 50] -> [10, 30, 50]으로 원하는 답인 [10, 40, 50]과 다른 답이 나온다. 이를 정확하게 구하는 문제는 14003번: 가장 긴 증가하는 부분 수열 5에서 연습해 볼 수 있다(풀이).

 

코드

---

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N, cnt;
int arr[1000001], dp[1000001];
vector<int> v, ans;

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> arr[i];

	v.push_back(arr[1]);

	for (int i = 2; i <= N; i++)
	{
		if (v[cnt] < arr[i])
		{
			v.push_back(arr[i]);
			cnt++;
		}
		else
		{
			// 같거나 작은 위치를 lower_bound로 찾음
			int pos = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
			v[pos] = arr[i];
		}
	}

	cout << v.size();
}