C++ / 백준 / 11053 / 가장 긴 증가하는 부분 수열

문제

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

문제풀이

자기 자신도 길이에 포함시키므로 DP 배열의 값을 1로 초기화한다.

이중 반복문을 사용하면 간단히 풀린다.

DP[y]는 y까지의 수열에서 가장 긴 부분의 수열 길이를 의미한다.

y는 1부터 N까지, x는 1부터 y까지 DP[y]는 DP[x]의 값들을 계속 비교하면서 가장 큰 값+1을 집어넣는다.

 

코드

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

int main() {
	int N = 0;
	cin >> N;
	vector<int>Arr(N, 0);
	vector<int>DP(N, 1);
	int y = 0, x = 0;
	for (x = 0; x < N; ++x) {
		cin >> Arr[x];
	}
	int answer = 0;
	for (y = 0; y < N; ++y) {
		for (x = 0; x < y;++x) {
			if (Arr[x] < Arr[y]) {
				DP[y] = max(DP[y], DP[x] + 1);
			}
		}
		answer = max(answer, DP[y]);
	}
	cout << answer;
}