[백준/C++] 11053번: 가장 긴 증가하는 부분 순열

Problem

---

Solution

---

먼저 수열 A의 크기를 입력 받고 for문을 활용해 수열 A의 원소들을 입력 받는다

dp 배열을 모두 1로 초기화한다.

0부터 i-1까지 순회하면서 arr[i] 보다 작은 원소들을 찾고, 작은 원소 arr[j]를 찾으면 dp[i]와 dp[j]+1 중 큰 값을 dp[i]에 저장한다. 

마지막으로 dp배열 중 가장 큰 값을 찾아 result에 저장한 후 출력한다.

Answer

---

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

int arr[1001];
int dp[1001];

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

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < n; i++) {
		dp[i] = 1;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}

	int result = 0;
	for (int i = 0; i < n; i++) {
		result = max(result, dp[i]);
	}

	cout << result << '\n';

	return 0;

}

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