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

📝 문제풀이 과정

---

• BOJ:11053 문제에서 코드 한 줄만 바꿔주면 된다.
• DP 배열은 각 원소에서 가질 수 있는 가장 긴 감소하는 부분 수열의 길이를 저장한다.
• i번째에서 DP[i] = 1, 즉 길이 1로 초기화하고, i번째 전까지 원소 값과 i번째 값과 비교해서 A[i] < A[j]이면 DP[i]를 설정해준다.
• 이때, 가장 긴 부분 수열의 길이를 구하는 것이므로 DP[j]에서 i번째를 더하면 +1이 되는 DP[j]+1과, DP[i]에서 더 큰 값을 가져온다. => max 함수 사용
• 마지막에 DP 배열에서 가장 큰 값을 max_element 함수로 출력한다.

 

 

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <algorithm>
using namespace std;

int main(){
    int N;
    scanf("%d", &N);

    int A[N] = {};
    int DP[N] = {};

    for(int i=0; i<N; i++) scanf("%d", &A[i]);

    for(int i=0; i<N; i++){
        DP[i] = 1;
        for(int j=0; j<i; j++){
            if(A[i] < A[j]) DP[i] = max(DP[i], DP[j]+1);
        }
    }
    printf("%d", *max_element(DP, DP+N));
}

 

 

 

👏 결과

---