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

#문제

www.acmicpc.net/problem/11722

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

#풀이 & 학습한 내용

supremo7.tistory.com/92에서 푼 문제에서 부호만 바뀐 문제이다. 맨 처음 그 수만 선택되었을 때인 1을 모두 넣어주고, 그 수 앞의 수들에 대해 p[j] > p[i] && dp[j] + 1 > dp[i]을 통해 dp[i]값을 결정한다. 그리고 dp배열 중 최댓값으로 답을 출력해준다. 

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int p[1002];
int dp[1002];
 
int main(void) {
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> p[i];
    //input end
 
    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_11722.cpp

HoYoungChun/BOJ_algorithm