티스토리 뷰

728x90

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;
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/10   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함