[Softeer] 징검다리

링크 : https://softeer.ai/practice/info.do?idx=1&eid=390

#include <iostream>
#include <vector>

using namespace std;

int getPosition(vector<int> v_ans, int target)
{
	int middle = -1;
	int first = 0;
	int last = v_ans.size() - 1;
	while (1)
	{
		middle = (first + last) / 2;
		if (first >= last) break;
		if (v_ans[middle] > target)
			last = middle;
		else
			first = middle + 1;
	}
	return last;
}

int getAns(vector<int> v_stone)
{
	int cntStone = 0;
	vector<int> v_ans;
	v_ans.push_back(v_stone[0]);
	for (int i = 1; i < v_stone.size(); i++)
	{
		// v_ans와 지금 넣는 v_stone을 비교
		if (v_ans[v_ans.size() - 1] < v_stone[i])
			v_ans.push_back(v_stone[i]);
		else
			// 이분탐색으로 위치확인 후 삽입
			v_ans[getPosition(v_ans, v_stone[i])] = v_stone[i];
	}
	int de = 1;

	
	return v_ans.size();
}

int main()
{
	int N;
	cin >> N;

	vector<int> v_stone;
	for (int i = 0; i < N; i++)
	{
		int stone;
		cin >> stone;
		v_stone.push_back(stone);
	}

	cout << getAns(v_stone);
	return (0);
}