백준 11053: 가장 긴 증가하는 부분 수열(DP)

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

어제의 알고리즘 대실패는 나로 하여금 나 자신이 빡통이라는걸 절절히 인정하는 그러한 계기가 되었다.

그래서 오늘 문제는 바로 갓무위키를 찾아보았다.

부분수열이 뭔지 까먹었기도 하고ㅎ

꺼라위키 정의 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다. 예를 들어 다음 수열이 주어졌다고 하자. 3 5 7 9 2 1 4 8 위 수열에서 몇 개의 수를 제거해 부분수열을 만들 수 있다. 3 7 9 1 4 8 (5, 2 제거) 7 9 1 8 (3, 5, 2, 4 제거) 3 5 7 8 (9, 2, 1, 4 제거) 1 4 8 (3, 5, 7, 9, 2 제거) 이들 중 세번째, 네번째 수열은 오름차순으로 정렬되어 있다. 이들을 '증가 부분 수열'이라고 한다. 그리고 이런 증가 부분 수열 중 가장 긴 수열을 '최장 증가 부분 수열 (LIS)'이라 한다. 부분수열 3 5 7 8은 LIS이다. 한 수열에서 여러 개의 LIS가 나올 수도 있다. 예를 들어 수열 5 1 6 2 7 3 8 에서 부분수열 1 2 3 8 5 6 7 8 은 모두 길이가 4인 LIS이다.

부분수열은 간단히 말해서 임의의 수열 A에서 A의 원소를 포함하는 또다른 수열 B라고 보면 된다.

여기서 수열이라고 해서 좀 혼란스러웠는데, 수열은 보통 일정한 규칙이 존재하는 수의 집합이라고 봐야 하지만 여기선 없다고 봐도 상관 없다.

즉 걍 숫자 집합인데, 부분수열은 그냥 부분집합이다. 대신 숫자의 순서가 보장되어있는 집합이지

꺼라위키도 설명을 그지같이 했다. 몇 개의 숫자를 제거한다니, 제거하는 규칙이 있어야하는것마냥 설명해놓곤

걍 수열 A의 숫자 몇개 추려서 다른 수열 B 만들면 그게 A의 부분수열이다.(순서는 반드시 보장되어야 한다. 자세한 예시는 꺼라위키 정의 참고)

암튼, 그런 부분수열중에 오름차순으로 되어 있는 수열 x중 사이즈가 가장 큰 수열의 사이즈를 반환하는 문제다.

꺼라에서는 n제곱으로 푸는 방법과, n로그n으로 푸는 방법 둘 다 설명해놨는데 n제곱으로 풀어봤더니 통과된다.

알고리즘 푸는 방법은 혼자서 생각 못할 것 같아 어쩔 수 없이 봤지만...그래도 코드 구현은 직접 했다...

나도 똑똑해졌으면 좋겠구만

#include <iostream>
#include <algorithm>
 
int seq[1010];
int dp[1010];
 
bool cmp(int first, int second)
{
    if (first > second)
        return true;
    else
        return false;
}
 
int main()
{
    int N;
    std::cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int m = dp[0];
        for (int j = 0; j < i; ++j)
            if (seq[i] > seq[j] && dp[j] > m)
                m = dp[j];
        dp[i] = m + 1;
    }
    std::sort(dp, dp + N + 1, cmp);
    std::cout << dp[0];
    return 0;
}

여기서 sort를 사용했는데, 사실 max 변수 하나 만들어서 dp중 가장 큰 수를 max에 담아 출력하기만 하면 더 빠를 것이다

나는 그냥 좀 더 깔끔해보이려고 이렇게 뺐다. 문제는 없이 통과되던데

nlogn으로 푸는 방법

#include <iostream>
 
int seq[1010];
int dp[1010];
 
int main()
{
    int N;
    std::cin >> N;
    int back = 0;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> seq[i];
        int it = 1;
        while (dp[it] != 0)
        {
            if (dp[it] >= seq[i])
            {
                dp[it] = seq[i];
                break;
            }
            ++it;
        }
        if (dp[it] == 0)
        {
            dp[it] = seq[i];
            back = it;
        }
    }
    std::cout << back;
    return 0;
}

설명은 귀찮아서 생략

일케 하면 빠른대신에 모든 데이터들의 증가부분수열을 저장할수는 없다.