[백준 11722] 가장 긴 감소하는 부분 수열

0. 제목

• 백준 11722 가장 긴 감소하는 부분 수열
• BOJ 11722 가장 긴 감소하는 부분 수열
• C++ 11722 가장 긴 감소하는 부분 수열

---

1. 문제

https://www.acmicpc.net/problem/11722

---

2. 풀이

• DP 방식을 이용하였다.
• 먼저 모든 dp[i] 값을 나올수 있는 최소값인 1로 초기화 시킨다.
• dp[i]를 구하기 위해서는 다음과 같은 과정을 거쳐야 한다. 해당 인덱스의 배열 값(A[i])과 그 이전 값들을 비교한다. A[i]가 이전 값들보다 작으면 1씩 증가해주면 된다고 생각할 수 있다.
• 그러나 그렇게 하면 오류가 발생한다. 각각의 전 dp값들과 비교하지만 dp[i] < dp[j] + 1 (j는 1부터 i-1까지)을 만족해야한다. 작은 수로 갱신이 되면 안되기 때문이다.
• 그렇게 나온 dp[i]값들을 max와 비교해가면서 max값을 갱신해 나간다. 그렇게 나온 max 가 정답이다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int N;
    int A[1001];
    int dp[1001];
    int max = 0;
    
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> A[i];
    
    for(int i = 1; i <= N; i++){
        dp[i] = 1;
        for(int j = 1; j < i; j++){
            if(A[i] < A[j] && dp[i] < dp[j]+1)
                dp[i] = dp[j] + 1;
        }
        if(max < dp[i])
            max = dp[i];
    }
    cout << max << '\n';
    
    return 0;
}