[백준 11053] 알고리즘 45일차 : 가장 긴 증가하는 부분 수열

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

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

동적계획법 C++

가장 긴 증가하는 부분 수열을 구하는 문제

 

접근 방법

DP라서 뭔가 2중 for문은 안될 것 같다고 생각하다가 최대 N이 1000이고 제한시간이 1초면

2중 for문도 되겠다 싶어서 그렇게 구현했다.

이번에도 각 인덱스 까지의 최대길이를 갖고 있는 배열을 사용했다.

다만 2중 for문을 사용해야 했던 이유는 수열의 시작지점이 가변적이기 때문이다.

그래서 본인 전까지의 모든 인덱스를 검사하면서

그 중 본인을 포함했을때 증가하는 부분 수열이 성립하면서 가장 긴 길이를 저장할 수 있도록 했다.

 

소스코드

#include <iostream>
using namespace std;

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

    int num[n];
    int length[n];
    int max = 0;
    for(int i = 0 ; i < n ; i++){
        cin >> num[i];
        length[i] = 1;
        for(int j = 0 ; j < i ; j++){
            if(num[j] < num[i] && length[j] >= length[i]){
                length[i] = length[j]+1;
            }
        }
        if(max < length[i])
            max = length[i];
    }
    
    cout << max;
    return 0;
}