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

문제 : 11053

풀이 point

N의 크기가 1,000이므로 $N^2$을 보아도 시간초과는 나지 않는다.

i를 0부터 N까지, j를 0부터 i까지 옮기면서 기준 값 arr[i]보다 작은 값들이 있는지 본다. 작은 값이 있을 경우 dp[i]와 dp[j]+1중 누가 가장 큰지를 비교한다.

dp[i] = std::max(dp[i], dp[j] +1)
-> 가장 큰 값을 고름으로써 가장 긴 증가하는 부분 수열을 택하는 것이다.

풀이 방법

i = 0, j = 0

i = 1, j = 0, 1

i = 2, j = 0, 1, 2

이런식으로 구현하면 된다.

코드

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

#include <iostream>
#include <algorithm>

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

int main (){

    int N;
    std::cin >> N;

    for(int i{0}; i<N; ++i) std::cin >> arr[i];

    std::fill(dp, dp+N, 1);

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

    std::cout << *std::max_element(dp, dp+N);

    return 0;
}