백준 11568번 민균이의 계략 C++

출처 : https://www.acmicpc.net/problem/11568

 

문제를 한줄로 요약하자면 가장 긴 증가하는 부분 수열을 구하는 것이다.

다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

처음에 수열의 길이를 저장하는 dp테이블을 모두 1로 초기화 시킨다. (자신만 있을 경우 수열의 길이는 1)

원소들을 처음부터 검사하면서 자신의 앞에 있는 모든 원소들을 비교하다가 만약 자신보다 값이 작은 값을 찾으면 자신이 그 수열에 포함된다면 증가하는 수열의 길이가 늘어나는 것이기 때문에 찾은 값의 수열의 길이 중 가장 큰 값을 저장한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	int n;
	cin >> n;
	vector<int> v(n);
	vector<int> dp(n, 1);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	dp[0] = 1;
	int ans = 1;
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (v[i] > v[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		ans = max(ans, dp[i]);
	}
	cout << ans;
};