[Softeer] 징검다리

문제

접근 방법

• LIS 문제, dp 이용하여 해결

나의 풀이 - C++

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

using namespace std;

int main(int argc, char** argv)
{	int n;
	scanf("%d", &n);

	vector<int> height(n);
	vector<int> dp(n, 1);


	for(int i = 0; i < n; ++i){
		cin >> height[i];
	}
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < i; ++j){
			if(height[i] > height[j]){
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	cout << *max_element(dp.begin(), dp.end()) << "\n";

	return 0;
}