본문 바로가기
알고리즘

[백준 11722] 알고리즘 48일차 : 가장 긴 감소하는 부분 수열

by SiO2whocode 2020. 8. 21.
반응형

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

 

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

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  �

www.acmicpc.net

동적계획법 C++

이번엔 감소하는 부분 수열이다.

 

접근 방법

가장 긴 증가하는 부분수열에서 감소하는 부분수열로 바뀌었을 뿐이다.

비교할때 이 점을 유의해서 비교하면 된다.

 

소스코드

#include <iostream>
using namespace std;

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

    int num[n];
    int length[n];
    int max_length = 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 < length[i])
            max_length = length[i];
    }
    
    cout << max_length;
    return 0;
}
반응형

댓글0