백준 1965번: 상자넣기 (C++)

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

1965번: 상자넣기

---

Solved By: LIS

 

몇 달만에 풀어본 LIS 문제였습니다. 본인 이전에 작은 값이 없으면 그 값은 1을 가진다는 걸 인지 못 한 채로 계속 틀렸었습니다. 그걸 인지하니 바로 풀리더군요.

#include <iostream>
#define MAX 1001
using namespace std;

int n;
int arr[MAX];
int cache[MAX];

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
    }
    
    int answer = 0; // maxValue
    
    for(int i = 1; i <= n; i++){
        cache[i] = 1; // init, 이전 index에 아무 것도 없다면 본인 자체로 길이 1을 차지
        for(int j = 1; j < i; j++){
            if(arr[j] < arr[i]){
                cache[i] = max(cache[i], cache[j] + 1);
            }
        }
        answer = max(answer, cache[i]);
    }
    
    cout << answer;
    return 0;
}