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

가장 긴 감소하는 부분 수열

 

시간 제한             메모리 제한             제출             정답             맞힌 사람             정답 비율

 

1 초

256 MB

27538

17350

14150

64.024%

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1 복사

6
10 30 10 20 20 10

예제 출력 1 복사

3

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, a[1004], cnt[1004], ret=1;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //1. 입력받기
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    //2. 감소하는 부분수열 만들기
    fill(cnt, cnt+1004, 1);
    for (int i=0;i<n;i++){
        for (int j=0;j<i;j++){
            if(a[j]> a[i] && cnt[i]<cnt[j]+1){
                cnt[i]=cnt[j]+1;
            }
            ret=max(ret,cnt[i]);
        }
    }
    //3. 출력하기
    cout << ret;

}

 

주의할 점

• ret의 기본값은 1이다. 0 0 0 0 0 일경우에 감소하는 부분수열의 개수는 1이기 때문이다.