[백준 알고리즘/C++] 11053 가장 긴 증가하는 부분 수열

 

 

수열 A = {10, 20, 10, 30, 20, 50} 인 경우

가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고 수열의 길이는 4가 된다.

수열이 주어졌을 때 가장 긴 증가하는 부분 수열의 길이를 출력하는 문제

 

 

만약 {10, 12, 11, 12, 13, 15, 16, 18, 30} 이렇게 입력받는다면

12를 빼고 {10, 11, 12, 13, 15, 16, 18, 30} 이 가장 긴 수열이다

이걸 어떻게 판단하느냐.. 

 

증가하는 수열의 길이를 dp배열에 넣고, 계속 비교해가며 가장 긴 수열을 찾으면 된다

dp[i]에 1을 넣어두고, A[1]부터 A[i-1]번째 수까지 A[i]와 비교하는 아주 dp스러운 문제..

A[j](1 ≤ j < i) 번째 수가 A[i]보다 작을 때 마다 dp[i]와 dp[j]+1을 비교하여 더 큰 값을 dp[i]에 넣어주면 됨

이걸 아이패드 없이 친절하게 설명할 자신이 없다

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n, input[1001] = { 0, }, arr[1001] = { 0, }, res = 1;
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> input[i];
        arr[i] = 1;
 
        for (int j = 1; j < i; j++) {
            if (input[i] > input[j]) {
                arr[i] = max(arr[i], arr[j] + 1);
            }
 
            if (arr[i] > res) {
                res = arr[i];
            }
        }
    }
 
    cout << res;
}