[Dynamic Programming] 가장 긴 증가하는 부분 수열 (LIS) - 백준 11053번

11053번: 가장 긴 증가하는 부분 수열

문제 파악 실패

• for문 한번으로 지금까지 나온 수보다 크면 무조건 수열에 추가
• 반례 1 8 6 2 3 → 내가 생각한 알고리즘 : 1 8 (2), 정답 : 1 2 3 (3)

Dynamic Programming

규칙을 찾거나 일반식을 찾는 것이 키 포인트!!

풀이

• 두 vector를 사용
  • A[i]는 value
  • D[i]는 length
• 전에 나온 모든 숫자들보다 현재 숫자가 더 클 때, D vector에 있는 최댓값 + 1을 D[i]에 넣는다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> vec;
    vector<int> D(n, 1);
    for(int i=0; i<n;i++) {
        int a;
        cin >> a;
        vec.push_back(a);
    }

//---풀이-----------------------------------
    for(int i=0;i<n;i++) {
       for(int j=0;j<i;j++) {
            if(vec[i] > vec[j]) {
                D[i] = max(D[i], D[j]+1);
            }
       }
    }
//-------------------------------------------
    sort(D.begin(), D.end());
    cout << D.back() << "\n";
}

• 이중 for문을 사용하여
  • vec[i]을 한바퀴 도는 용
  • 뒤에 나온(i보다 작은) vec vector의 원소 확인
• 이전 vec vector의 원소보다 현재의 숫자가 더 클 경우 가지고 있는 D[i]와 비교 후 큰 것을 매번 업데이트

⇒ 비효율적..!

Time Complexity : O(n^2)

근데 다른 사람들은 다 이렇게 했던데 두 번째 for문 없이 한번으로도 가능 할 것 같은데…