Beakjoon 11722 가장 긴 감소하는 부분 수열

31 Jan 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/11722

나의 풀이

이 문제는 DP로 해결할 수 있다.
DP[i]는 마지막 값이 A[i]인 가장 긴 감소하는 부분 수열의 길이를 의미한다.
예를 들어, 수열 A = {10, 30, 10, 20, 20, 10}인 경우
DP[0] = 1
DP[1] = max(DP[0]+1, 1) # 단 A[0] > A[1] (감소하는 수열이기 위해)
DP[2] = max(DP[0]+1, DP[1]+1, 1) # 단 A[0] > A[2] , A[1] > A[2] (감소하는 수열이기 위해)
…..
DP[5] = max(DP[0]+1, DP[1]+1, DP[2]+1, DP[3]+1, DP[4]+1, 1)

풀이 코드 : 11722 가장 긴 감소하는 부분 수열

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int DP[1000];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<int> A;
    int N, num;
    cin>>N;
    
    for(int i=0;i<N;i++){
        cin>>num;
        A.push_back(num);
        DP[i] = 1;
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<=i;j++){
            if(A[i] < A[j]){
                DP[i] = max(DP[j]+ 1, DP[i]);
            }
        }
    }
    int answer = 0;
    for(int i=0;i<N;i++){
        if(DP[i] > answer)
            answer = DP[i];
    }
    cout<<answer;
}

채점결과