[C++] 백준 12015. 가장 긴 증가하는 부분 수열 2

🌽 문제

🥕 입출력

🥔 풀이

옛날에 GPT가 알려준 추가 풀이가 이 문제의 풀이였음을 알았다.
lis 자체를 구할 땐 이 풀이를 사용할 수 없고, 길이 출력 시 사용할 수 있다.
입력받은 수가 lis 중 가장 크면 push하고,
그렇지 않으면 들어갈 수 있는 자리에 치환해준다.
근데 치환하는 이유는 잘 와닿지 않아서 담에 다시 좀 봐야될 것 같다.

🥬 코드

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

int N;
vector<int> v, lis(1);

void solution(int num) {
	auto idx = lower_bound(lis.begin(), lis.end(), num);
	if (idx == lis.end()) lis.push_back(num);
	else *idx = num;
}

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

	cin >> N;
	v.resize(N);
	cin >> lis[0];
	for (int i = 1; i < N; i++) {
		cin >> v[i];
		solution(v[i]);
	}
	cout << lis.size();

	return 0;
}

🥜 채점

시간초과는 dp 풀이