[백준 11053] 가장 긴 증가하는 부분 수열

0. 제목

• 백준 11053 가장 긴 증가하는 부분 수열
• BOJ 11053 가장 긴 증가하는 부분 수열
• C++ 11053 가장 긴 증가하는 부분 수열

---

1. 문제

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

---

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] = {0};
    int dp[1001] = {0};
    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[j]+1 > dp[i])
                dp[i] = dp[j] + 1;
        }
        if(dp[i] > max)
            max = dp[i];
    }
    
    cout << max << '\n';
    return 0;
}
 

다른 풀이 

#include <iostream>
#include <algorithm> 
 
using namespace std;
 
int main()
{
 
    int n;
    int dp[1000] = {};
    int arr[1000] = {};
    int sum = 0;
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
 
    
 
 
    for (int i = 0; i < n; i++)
    {
        dp[i] = 1;
 
        for (int j = 0; j < i; j++)
        {
            if (arr[i] > arr[j])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        sum = max(sum, dp[i]);
    }
    
    cout << sum << endl;
}