[BOJ] 11053 가장 긴 증가하는 부분수열 - LIS

가장 긴 부분 수열의 길이를 출력하라고 했다.

이 경우, 숫자를 하나씩 추가해가며 수열을 만들어 준다.

마지막 원소보다 크기가 큰 원소가 들어오면(증가수열을 이루도록 하기 위해서)

원소를 추가해주고,

( 1 2 3 4 5 7 이였고 8 이 들어왔다 그러면 1 2 3 4 5 7 8 이 된다. )

마지막 원소보다는 크기가 작거나 같다면,

만들고 있는 수열의 원소들 중 해당 원소보다 작은것들중 가장 큰것과 바꿔준다.

( 1 2 3 4 5 7 이였고 6이 들어왔다 그러면 1 2 3 4 5 6 이 된다.)

7을 왜 6으로 대체 해도 될까.

길이를 구하라고 했다.  7을 6으로 대체해도 길이는 달라지지 않는다.

7을 6으로 대체한다면, 후에 오는 7을 취할수 있다.

 

마지막 원소를 대체하는 경우가 아닌 앞의 원소를 대체하는 경우를 보자.

예시를 보자.

 

수열이 진행되며 앞의 원소들을 차례로 대체하고 있다. 

이렇게 해도 관계가 없다는 것을 알 수 있다.

큰건 더하고

그렇지 않으면 대체 한다. 

수열의 길이는 유지 된다는 거다. 

코드로 구현한 결과는 다음과 같다.

#include <iostream>
#include <algorithm>
#include <vector>



int Cost[1001] = { 0 , };

std::vector<int> LIS;

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

	int N;

	std::cin >> N;

	for (int i = 1; i <= N; ++i)
		std::cin >> Cost[i];

	LIS.push_back(Cost[1]);

	for (int i = 2; i <= N; ++i)
	{
		int LISLastElement = LIS.back();
		int ElementCost = Cost[i];


		if (LISLastElement < ElementCost)
			LIS.push_back(ElementCost);

		else
			for (int k = 0; k < LIS.size(); ++k)
			if (ElementCost <= LIS[k])
			{
				LIS[k] = ElementCost;
				break;
			}
	}

	std::cout << LIS.size();

	return 0;
}