백준/11053번/가장 긴 증가하는 부분 수열/실버2

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

문제 설명

Site: Baekjoon
Number: 11053
Category: Dynamic Programming
Rank: Silver 2

가진 긴 증가하는 부분 수열을 학습하는 기본 문제.

수열 A가 주어졌을 때 A에서 가장 긴 증가하는 부분 수열의 길이를 출력하면 된다.

풀이는 두 가지 방법이 존재한다.

1. 모든 요소를 비교하며 오름차순 수열을 작성하며 수열 들의 길이를 비교하는 방법

이 방법은 시간 복잡도 O(N²)이 나오기 때문에 권장하지 않는 방법이다.

1. 수열을 하나 만들고 요소를 흝어가며 갱신하는 방식

이 방법은 모든 요소를 한번 흝으며 수열에서는 탐색을 진행하기 때문에 시간 복잡도 O(NlogN)이 나온다

필자는 2번 풀이를 채택하였다

풀이는 수열을 저장할 배열 arr을 최대 크기로 선언하고, 수열의 원소들을 cin을 통해 입력받으며 연산을 진행한다.

입력받은 원소 num을 현재 있는 수열에서 lower_bound를 통해 iterator 값을 가져온다.
이 값은 현재 수열에 num보다 큰 값이 있는 경우 그 iterator, 큰 값이 없는 경우 마지막 값의 다음 iterator를 가져온다.

이렇게 가져온 iterator에 num값을 넣는다

• num보다 큰 값이 있는 경우, iterator에 있는 값을 바꿔주어 이 후에 들어올 숫자에 대한 기준을 낮추는 의미.
• num보다 큰 값이 없는 경우, 수열의 길이 len이 하나 늘어나며 증가하는 부분 수열의 길이가 늘어남을 의미.

모든 요소를 입력받은 후의 len 값이 정답이 된다.

#include <iostream>

using namespace std;

int arr[1001];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, len = 0;
	cin >> N;

	for(int i = 0; i < N; i++)
	{
		int num;
		cin >> num;

		auto iter = lower_bound(arr + 1, arr + len + 1, num);
		*iter = num;

		if (iter == arr + len + 1)
			++len;
	}

	cout << len;

	return 0;
}