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

[yeonddori]

문제: https://www.acmicpc.net/problem/11725

문제 설명

주어진 수열에서 가장 긴 감소하는 부분 수열(LDS, Longest Decreasing Subsequence)을 구하는 문제입니다.

문제 풀이

이 문제는 동적 계획법(DP)을 활용하여 해결할 수 있습니다.
DP 배열 dp[i]는 i번째 원소를 마지막으로 포함하는 LDS의 길이를 저장합니다.

• 점화식
  dp[i] = max(dp[i], dp[j] + 1) (단, j < i이고 A[j] > A[i])

• 초기값
  모든 dp[i]를 1로 초기화합니다. 이는 최소한 각 원소 자체로 LDS를 만들 수 있기 때문입니다.

• 결과
  dp 배열의 최댓값이 가장 긴 감소하는 부분 수열의 길이가 됩니다.

코드

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<int> A(N), dp(N, 1);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    for (int i = 1; i < N; i++) {
        for (int j = 0; j < i; j++) {
            if (A[j] > A[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    cout << *max_element(dp.begin(), dp.end());
    return 0;
}

후기

거저먹으려고 비슷한 문제 푼 거 절대적으로 맞습니다.. 헤헤