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

#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#define SIZE 1000+1
 
using namespace std;
 
int main() {
    vector<int> dp(SIZE, 0);
    vector<int> numbers(SIZE, 0);
 
    int n;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        cin >> numbers[i];
    }
 
    dp[1] = 1;
 
    //dp[i]: i번째 수가 무조건 골라지는 경우 LIS
    for (int i = 2; i <= n; i++) {
        int maxVal = INT_MIN;
        for (int j = 0; j <= i - 1; j++) {
            if(numbers[j]<numbers[i])
                maxVal = max(maxVal, dp[j]);
        }
        dp[i] = maxVal + 1;
    }
 
    int result = INT_MIN;
    for (int i = 1; i <= n; i++) {
        //n번째 수 안고를 수도 있으니까 dp[n]이 아닌 dp[n]까지의 최대값을 구한다
        result = max(result, dp[i]);  
    }
    
    
    cout << result;
 
 
    return 0;
}

 

LIS를 구하는 법

- 처음부터 현재 인덱스 전까지의 값을 살펴보면서 현재 인덱스 값보다 작은 값들의 최대 dp + 1

여기까지 하면 dp[i]는 i번째 수를 무조건 골랐을 때 LIS

- 이런 식으로 i==n까지 dp 구해놓기

- dp[n]을 출력하면 n번째 수를 무조건 고를때의 LIS이다. n번째 수를 안고를 수도 있기때문에 dp[n]이 아닌 dp[n]까지의 수중에서 가장 큰 값을 출력

 

처음에 문제 풀 때 dp[i]에 i번째 수열까지의 LIS를 넣고 마지막에 dp[n]을 출력하려고 했음

그래서 i번째 수를 고를지 말지를 정하는 과정에서 어려웠는데

dp[i]를 i번째 수열까지의 LIS가 아닌 i번째 수를 무조건 골랐을 때의 LIS라고 하고 마지막에 dp[n]까지의 max값을 출력하면 훨씬 쉽구나ㅠㅠ