백준 2352번 반도체 설계 (c++)

 

꼬임이 없다는 것은 오름차순으로 정렬되어야 한다는것

즉 가장 긴 증가하는 부분수열을 구하는 문제이다

하지만 n이 40000이나 되기 때문에 일일이 비교하면 시간초과가 되므로 이분탐색 기반 알고리즘을 이용한다

 

cin >> n;
for (int i = 1; i <= n; i++)
{
	int a;
	cin >> a;
	if(arr.empty()) arr.push_back(a);
	else
	{
		int idx = lower_bound(arr.begin(), arr.end(), a) - arr.begin();
		if (idx >= arr.size()) arr.push_back(a);
		else arr[idx] = a;
	}
}

 

숫자를 받으면서 바로 증가하는 수열을 만들어준다

lower_bound는 배열에서 지정한 수보다 크거나 같은 숫자가 몇번째 인덱스에서 처음 나오는지 반환한다

iter로 반환하므로 .begin()을 빼주면 다음 인덱스를 구할 수 있다

지정한 수가 가장 큰 수면 end() 를 반환할테니 그럴 경우 push_back으로 넣어주고

아니면 그 인덱스의 수를 교체한다

cout << arr.size() << endl;

만들어진 수열의 길이를 출력하면 끝

 

가장 긴 증가하는 부분수열을 lower_bound를 통해 구하는 문제이다

생긴것만 다르고 풀이는 다른 이런 문제가 몇개 있어서, 문제의 본질을 얼마나 빨리 파악하느냐가 중요하다