[C++] 백준 11053번 : 가장 긴 증가하는 부분 수열 (S2)

#문제

www.acmicpc.net/problem/11053

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

 

#풀이 & 학습한 내용

시간복잡도를 O(N)으로 구현하려 시도했지만 실패하고 O(N^2)로 구현했다. dp배열에 그 위치를 수열의 마지막으로 갖는 최대 증가하는 부분 수열의 길이를 저장했다. j가 1부터 i까지 움직이며 p[j]<p[i] && dp[j] + 1>dp[i] 조건이 만족되면 갱신되도록 for문을 구성했다. 그리고 문제에서 구하는 최댓값은 dp배열의 값들 중 최대이므로 for문을 통해 최댓값을 구한다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int dp[1001];
int p[1001];
 
int main(void) {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> p[i];
    }
 
    for (int i = 1; i <= N; i++) {
        dp[i] = 1;
        for (int j = 1; j <= i; j++) {
            if (p[j]<p[i] && dp[j] + 1>dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }
 
    int max = dp[1];
    for (int i = 2; i <= N; i++) {
        if (max < dp[i])
            max = dp[i];
    }
 
    cout << max << '\n';
}

 

github.com/HoYoungChun/BOJ_algorithm/blob/master/Dynamic_Programming/BOJ_11053.cpp

HoYoungChun/BOJ_algorithm