📝 문제

📌 풀이

• 가장 긴 증가수열을 찾는 문제로 시간복잡도가 가장 작은 이진탐색을 이용해야한다.

• 이진 탐색을 이용하여 가장 긴 증가수열에 적용하면 실제 가장 긴 증가수열을 찾지는 못한다. 하지만 가장 긴 증가수열의 길이을 알 수 있어서 이를 활용하면 풀 수 있다.

• 가장 첫번째 값을 우선 LIS 배열에 넣고 LIS 끝 값과 넣으려는 값을 비교한다.

  • 넣으려는 값이 더 크다면 증가수열을 유지할 수 있기 때문에 바로 배열 마지막에 추가해주어 LIS 길이를 늘린다.
  • 넣으려는 값이 크지 않다면 LIS 배열 중에서 lower_bound를 이용하여 넣으려는 값 이상의 값을 가지는 첫번째 인덱스를 찾아 그곳에 넣으려는 값을 넣는다. 이렇게 하는 이유는 가장 긴 증가하는 수열을 만들기 위해서는 현재 LIS 배열의 끝 값이 최대한 작아야 유리하기 때문에 그 상태를 만들어주기 위함이다.

• 예시
  

💻 코드

//난이도 : 골드2
//시작 : 19:15
//끝 :
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int T;
	cin >> T;
	for (int t = 0; t < T; t++) {
		int N, K;
		cin >> N >> K;
		vector<int> arr;
		for (int i = 0; i < N; i++) {
			int tmp;
			cin >> tmp;
			arr.push_back(tmp);
		}
		vector<int> LIS;
		LIS.push_back(arr[0]);  // 가장 첫번째 값 바로 LIS 배열에 넣기
		for (int i = 1; i < N; i++) {
			if (LIS[LIS.size() - 1] < arr[i]) {  // LIS 배열의 끝 값보다 넣으려는 값이 큰 경우
				LIS.push_back(arr[i]);  // LIS 배열 끝에 추가
			}
			else {  // 그렇지 않은 경우
				int pos = lower_bound(LIS.begin(), LIS.end(), arr[i]) - LIS.begin();  // LIS 배열에서 넣으려는 값 이상의 값을 가지는 가장 첫번째 인덱스
				LIS[pos] = arr[i];  // 그 위치에 넣으려는 값을 대치한다. -> 맨 끝의 값이 바뀌는 경우 LIS 맨 끝의 값을 최대한 작게 유지해주며 이는 LIS를 만들 수 있는 조건이다.
			}
		}
		cout << "Case #" << t + 1 << '\n';
		if (LIS.size() >= K) {
			cout << 1 << '\n';
		}
		else {
			cout << 0 << '\n';
		}
	}

	return 0;
}